백준 10026: 적록색약의 두 시야를 DFS로 나누기

백준 10026번 ‘적록색약’은 같은 그림을 두 가지 기준으로 보고 구역 수를 세는 문제입니다. 기준마다 연결된 것으로 판단하는 색의 조건이 다릅니다.

방문 기록도 두 개로 나눕니다

일반적인 시야에서는 현재 칸과 다음 칸의 색이 같을 때만 이동합니다. 적록색약의 시야에서는 같은 색뿐 아니라 빨강과 초록 사이도 이동할 수 있습니다.

같은 색으로 취급하더라도 상하좌우로 이어지지 않은 칸은 서로 다른 구역입니다.

두 탐색이 서로의 방문 기록에 영향을 주지 않도록 normalVisited와 blindVisited를 따로 만들었고 각 기준에서 아직 방문하지 않은 칸을 발견하면 DFS를 시작해 구역 수를 하나 늘렸습니다. 당시 주의사항에는 BFS라고 적었지만 실제 구현은 재귀 DFS입니다.

당시 제출 코드

Java

import java.io.*;

class Main {

    static int N;
    static char[][] map;
    static boolean[][] normalVisited;
    static boolean[][] blindVisited;
    static int[] opsX = {-1, 1, 0, 0};
    static int[] opsY = {0, 0, -1, 1};
    static int[] count = new int[2];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        normalVisited = new boolean[N][N];
        blindVisited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!normalVisited[i][j]) {
                    normalDfs(i, j);
                    count[0]++;
                }
                if (!blindVisited[i][j]) {
                    blindDfs(i, j);
                    count[1]++;
                }

            }
        }

        bw.write((count[0]) + " ");
        bw.write(String.valueOf(count[1]));
        bw.flush();
    }

    public static void normalDfs(int x, int y) {
        normalVisited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int newX = x + opsX[i];
            int newY = y + opsY[i];

            if (-1 < newX && newX < N && -1 < newY && newY < N) {
                if (map[newX][newY] == map[x][y] && !normalVisited[newX][newY]) {
                    normalDfs(newX, newY);
                }
            }
        }
    }

    public static void blindDfs(int x, int y) {
        blindVisited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int newX = x + opsX[i];
            int newY = y + opsY[i];

            if (-1 < newX && newX < N && -1 < newY && newY < N) {
                if (    (map[newX][newY] == 'G' && map[x][y] == 'R') ||
                        (map[newX][newY] == 'R' && map[x][y] == 'G') ||
                        (map[newX][newY] ==  map[x][y])    ) {
                    if (!blindVisited[newX][newY]) {
                        blindDfs(newX, newY);
                    }
                }
            }
        }
    }
}