[백준] 10026번 적록색약

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   N * N인 그리드의 각 칸에 R(빨간), G(초록), B(파랑) 중 하나를 색칠한 그림이 있을 때, 적록색약이 아닌 사람이 봤을 때의 구역 수와 적록색약인 사람이 봤을 때의 구역 수를 구하는 문제이다.

   적록색약은 R과 G의 차이를 거의 느끼지 못하며, 같은 색상이 상하좌우로 인접한 경우에 같은 구역에 속한 것으로 취급한다. 예제는 다음과 같다.

 

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

//적록색약O : 3개
//적록색약X : 4개

 

 

   첫째 줄에 N이 주어지고 둘째 줄부터 N개 줄에 그림이 주어진다. 제한 사항은 다음과 같다.

 

• 1 ≤ N ≤ 100
• 결과는 공백으로 구분하여 출력한다.

 

 

---

접근 방식

   DFS의 개념을 이용해 문제를 해결하였다. 적색색맹 여부에 따라 탐색해야 하는 색이 달라질 수 있기 때문에 각각 방문 여부를 저장할 수 있는 2차원 배열이 필요하다.

   우선 입력으로 주어진 2차원 배열 전체에 대해 해당 위치에서 탐색을 수행해야 하는지 결정해야 한다. 다음 예시를 보면 처음 위치의 색이 R인 것을 알 수 있다.

 

 

   즉, 현재 탐색할 색은 R이다. 현재 위치에서 인접한 4방향에 대해 탐색하며 R과 같은 색이 있는지 탐색을 진행한다. 방문한 곳에 대해서도 인접한 4방향 탐색을 수행한다. 이때 탐색 위치가 범위를 벗어나는 부분은 탐색을 진행하지 않는다.

 

 

   더 이상 찾는 색이 인접해있지 않은 경우 탐색이 종료된다. 탐색이 종료된 경우 하나의 영역을 찾은 것으로 판단하여 영역 카운트를 증가 시킨다.

 

 

   탐색 과정에서 방문했던 위치는 방문 여부를 저장해둬야 한다.

 

 

   이제 그 다음 위치로 넘어가 탐색 여부를 판단한다. 현재 탐색할 위치가 이미 이전에 방문했던 적이 있기 때문에 탐색을 수행하지 않고 넘어간다. 3번째까지는 이미 방문했기 때문에 4번째부터 탐색이 수행된다.

 

<적색생맹이 아닌 경우>

<적색색맹인 경우>

 

   이후 탐색은 위에서 했던 과정을 반복하며 최종적으로 구한 영역 카운트는 적색색맹이 아닌 경우의 결과이다. 적색생맹인 경우는 현재 탐색을 수행하는 색이 R이나 G인 경우에 대해 인접한 칸이 R이나 G인 경우 탐색을 진행하면 된다. 즉, 적색생맹이 아닌 경우는 같은 색만을 탐색하지만 적색색맹인 경우 R과 G를 동일한 색으로 판단하여 탐색을 진행한다. 

---

코드

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

public class 백준10026번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static char[][] input;
    //4방향 탐색을 위한 서언
    static final int[] X = {-1, 1, 0, 0};
    static final int[] Y = {0, 0, -1, 1};
    //방문 여부 저장
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        input = new char[N][N];

        for (int i = 0; i < N; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < N; j++)
                input[i][j] = tmp.charAt(j);
        }

        //0번째 인덱스는 적색생맹이 아닌 사람, 1번째 인덱스는 적색색맹인 사람
        int[] result = new int[] {0, 0};
        visited = new boolean[2][N][N];

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                //i가 0인 경우 적색색맹이 아닌 사람, i가 1인 경우 적색색맹인 사람
                for (int i = 0; i < 2; i++) {
                    //방문한 적이 없는 경우 탐색 진행
                    if (!visited[i][y][x]) {
                        DFS(x, y, input[y][x], i);
                        result[i]++;
                    }
                }
            }
        }

        System.out.println(result[0] + " " + result[1]);
    }

    public static void DFS(int x, int y, char color, int blind) {
        //2차원 배열의 범위를 벗어난 경우
        if (x < 0 || x >= N || y < 0 || y >= N) return;
        //이미 방문했던 경우
        else if (visited[blind][y][x]) return;
        //적색색맹이 아니면서 색이 다른 경우
        else if (blind == 0 && color != input[y][x]) return;
        //적색색맹이면서 색이 다르고, 둘 중 하나가 B인 경우
        //아스키코드값의 차의 절댓값을 이용하여 R, G인지 판단
        else if (blind == 1 && color != input[y][x]
                && Math.abs(color - input[y][x]) != 11) return;
        //방문 여부 저장
        visited[blind][y][x] = true;

        //4방향 탐색
        for (int i = 0; i < 4; i++)
            DFS(x + X[i], y + Y[i], color, blind);
    }
}