백준 10026 적록색약

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

• bfs를 이용해 풀이한다.
• 정상인과 색약은 초기조건이라 할 수 있는 맵이 다르기 때문에 각각 bfs를 따로 해줘서 답을 구한다.
• bfs의 동작원리는 같으므로 파라미터 인자로 다른 값을 넘겨줘 구분한다.
• 모든 맵의 좌표를 돌면서 방문처리 되지 않은 좌표를 기준으로 bfs를 한다.
• bfs를 하며 큐에 들어간 좌표는 방문처리를 한다.

---

코드

정답 코드

/**
 * 10026 - 적록색약
 *
 * bfs 풀이
 * 정상인이 보는 맵 - originalMap, 색약이 보는 맵 - weakMap으로 나눠서 풀이한다.
 * 두 경우 각각 bfs를 해준다.
 */


public class P_10026 {
    static int N;
    static char[][] originalMap; // 정상인의 맵
    static char[][] weakMap; // 색약의 맵
    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};
    static boolean[][] originalVisited; // 정상인의 맵 방문처리
    static boolean[][] weakVisited; // 색약의 맵 방문처리
    static Queue<Point> originalQueue; // 정상인의 bfs를 위한 Queue
    static Queue<Point> weakQueue; // 색약의 bfs를 위한 Queue
    static int originalAnswer; // 정상인의 답
    static int weakAnswer; // 색약의 답

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        originalMap = new char[N][N];
        weakMap = new char[N][N];
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < N; j++) {
                originalMap[i][j] = temp.charAt(j);
                weakMap[i][j] = temp.charAt(j);
                // 색약의 경우 G를 R로 바꿔서 맵을 채운다.
                if(weakMap[i][j] == 'G'){
                    weakMap[i][j] = 'R';
                }
            }
        }

        originalVisited = new boolean[N][N];
        weakVisited = new boolean[N][N];

        originalQueue = new LinkedList<>();
        weakQueue = new LinkedList<>();

        originalSol();
        weakSol();
        System.out.println(originalAnswer + " " + weakAnswer);

    }

    // 정상인의 답을 구하는 메서드
    // 모든 맵을 돌면서 방문처리가 안된 좌표만 Queue에 넣고 bfs를 통해 답을 구한다.
    static void originalSol() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!originalVisited[j][i]){
                    originalQueue.add(new Point(j,i));
                    originalVisited[j][i] = true;
                    bfs(new Point(j, i), originalQueue, originalMap, originalVisited);
                    originalAnswer++;
                }
            }
        }
    }

    // 색약의 답을 구하는 메서드
    // 모든 맵을 돌면서 방문처리가 안된 좌표만 Queue에 넣고 bfs를 통해 답을 구한다.
    static void weakSol() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!weakVisited[j][i]){
                    weakQueue.add(new Point(j,i));
                    weakVisited[j][i] = true;
                    bfs(new Point(j, i), weakQueue, weakMap, weakVisited);
                    weakAnswer++;
                }
            }
        }
    }

    // bfs 메서드
    // 정상인, 색약의 맵 조건이 다르기 때문에 파라미터로 다 넘겨준다.
    static void bfs(Point p, Queue<Point> queue, char[][] map, boolean[][] visited){
        while (!queue.isEmpty()){
            p = queue.poll();

            for (int i = 0; i < 4; i++) {
                int y = p.y + my[i];
                int x = p.x + mx[i];

                if(y>=0 && y<N && x>=0 && x<N && !visited[y][x]){
                    if (map[p.y][p.x] == map[y][x]){
                        visited[y][x] = true;
                        queue.add(new Point(y,x));
                    }
                }
            }
        }
    }

    static class Point{
        int y;
        int x;

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}