[백준_java] 적록색약(10026번) // dfs

문제

 

내 풀이, dfs

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

class Main {
    static int N;
    static char target;
    static int[] checkX = {0, 1, 0, -1};
    static int[] checkY = {1, 0, -1, 0};
    static char[][] rgb;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        rgb = new char[N][];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            rgb[i] = br.readLine().toCharArray();
        }
        int eye1 = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                target = rgb[x][y] ;
                if (target == 'R') {
                    rgb[x][y] = 'G';
                }
                if (!visited[x][y]) {
                    dfs(target, x, y);
                    eye1++;
                }
            }
        }
        visited = new boolean[N][N];
        int eye2 = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                target = rgb[x][y] ;
                if (!visited[x][y]) {
                    dfs(target, x, y);
                    eye2++;
                }
            }
        }
        System.out.println(eye1 + " " + eye2);
    }
    public static void dfs(char target, int x, int y) {
        if (!visited[x][y]) {
            visited[x][y] = true;
        } else {
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (x + checkX[i] >= 0 && x + checkX[i] < N
            && y + checkY[i] >= 0 && y + checkY[i] < N
            && rgb[x + checkX[i]][y + checkY[i]] == target) {
                dfs(target, x + checkX[i], y + checkY[i]);
            }
        }
    }
}

 

리뷰

2차원 배열 RGB가 표현 된다. 이를 하나의 그림으로 표현했을 때 각각 R, G, B의 색이 나뉘는 구역이 몇개인지 구분하여 일반적인 시선에서의 개수와 적록색약 시선에서의 개수를 출력해내는 문제이다.

 

예제 문제

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

위의 예제 문제를 그림으로 나타내보았다.

좌, 일반적인 시선 우, 적록색약의 시선

이와 같이 그림으로 표현해보면 구분하기가 쉬운데, 일반적인 시선으로 볼 땐 네개의 구역으로 나뉘고

적록색약의 시선은 R과 G의 분간이 어렵기 때문에 세개의 구역으로 나뉘는 걸 확인 할 수 있다.

 

dfs를 이용하여 풀어낸 문제이다.

rgb 배열과 같은 크기의 boolean 2 차원배열을 만든다.

rgb 배열의 0, 0  부터 방문하고 같은 위치의 boolean 배열의 값은 true로 바꿔준다. 현재 위치의 rgb 값중 하나(예시에선 

첫번째 R 값)를 target으로 지정해준다. 

순서대로 우, 하, 좌, 상 순서대로 돌며 해당 타겟과 같은 값을 가진 index는 boolean 배열에 방문 했다는 의미로 모두 true로 바꿔준다. 이렇게 한 사이클을 돌면 인접한 R 값을 가진 구역은 모두 true로 바뀌게 되며 그때 카운트를 1 (예시에선 eye1)올려준다.

 

이런식으로 모든 구역을 돌게 되는데 적록색약의 시선에서 카운터를 다시 해야하기 떄문에, 일반 시선 카운터를 돌 때 R 값을 G 값으로 바꿔주거나 G를 R로 바꿔주는 작업을 가미한다. 

 

이후 boolean 값을 초기하 한 뒤 다시 한번 배열을 돌며 적록색약의 카운트(예시에선 eye2)를 올려준다.

 

visited 배열을 활용해볼 수 있는 문제였다.