[JAVA] 백준 10026번 : 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    static int N;
    static Set<Character> set = new HashSet<>();
    static char[][] paint;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        set.add('R');
        set.add('G');
        paint = new char[N][];
        for (int i = 0; i < N; i++) {
            paint[i] = br.readLine().toCharArray();
        }
        StringBuilder sb = new StringBuilder();
        sb.append(bfs(false)).append(" ");
        sb.append(bfs(true));
        System.out.println(sb);
    }

    private static int bfs(boolean isCB) {
        Queue<Pos> queue = new LinkedList<>();
        visit = new boolean[N][N];
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visit[i][j]){
                    cnt++;
                    search(isCB, i, j, queue);
                }
            }
        }
        return cnt;
    }

    private static void search(boolean isCB, int x, int y, Queue<Pos> queue) {
        char color = paint[x][y];
        visit[x][y] = true;
        queue.add(new Pos(x, y));

        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx >= 0 && nx < N && ny >= 0 && ny < N && !visit[nx][ny]){
                    if ((isCB && set.contains(color) && set.contains(paint[nx][ny])) //적록 색약인 경우 실행될 추가 조건 (R, G 중 하나인지 체크)
                            || paint[nx][ny] == color) { //적록색약이 아닌 경우 색이 같은지만 체크
                        queue.add(new Pos(nx, ny));
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }

    private static class Pos {
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int x; int y;
    }
}

💡 BFS

풀이

- R/G/B 중 하나를 색칠한 그림. 몇 개의 구역으로 나뉘어져 있음

- 같은 구역 == 같은 색(or 색약의 경우, 색상 차이를 느끼지 못하므로 R, G를 동일한 색으로 취급)

  → 같은 색상이 상하좌우로 인접해 있음 ≒ 두 글자는 같은 구역에 속한다

 

EX) 적록 색약이 아닌 경우 4개의 구역, 적록 색약인 경우  R == G 이므로 3개의 구역만 볼 수 있음

(1)RRR(2)BB
(3)GG BBB
 BBB(4)RR
 BB   RRR
 RRRRR

• BFS 탐색으로 구역을 구분해 나가되, 색약은편의상  R, G를 동일하게 R로 취급해 탐색을 나간다.
• 색이 동일한 구역 탐색에 들어갈 때 마다 구역 +1 해줌