[DFS] 백준 - 10026번: 적록색약 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

10026번: 적록색약

 

 

문제의 요약은 적록색약은 R과 G로 되어있는 구역은 볼 수 없고, B는 따로 볼 수 있다.

정상인은 모든 색을 다른 구역으로 볼 수 있다.

 

그림으로 설명해보자면

적록색약이 아닌 사람

위의 그림은 적록색약이 아닌 사람이 볼 수 있는 색깔의 구역이고,

 

적록색약인 사람

위의 그림은 적록색약인 사람이 볼 수 있는 색깔의 구역이다.

 

그러면 DFS를 돌릴 때 조건을 주면 되는데 그 조건과 작동 순서는 다음과 같다.

 

적록색약이 아닌 사람)

1. map를 하나하나 읽는다.
2. 시작되는 좌표 지점의 색을 static으로 보관한다.
3. 선택된 색이 좌표 근처에 있는지 탐색을 한다.
4. 없으면 dfs를 탈출하여 카운팅을 한다.

 

적록색약인 사람)

1. map를 하나하나 읽는다.
2. 시작되는 좌표 지점의 색을 static으로 보관한다.
3. 선택된 색이 R 또는 G일 때 좌표 근처 두 색이 있는지 탐색을 하고, R, G는 하나로 생각한다.
4. 없으면 dfs를 탈출하여 카운팅을 한다.

 

코드

import java.util.Scanner;

public class Main {
    static char[][] map;
    static boolean[][] check;
    static int n;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    static char selectedColor;
    static boolean w; //적녹색약 여부

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        sc.nextLine();

        map = new char[n][n];
        check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = s.charAt(j);
            }
        }

        int count = 0;

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (!check[j][k]) {
                        selectedColor = map[j][k];
                        dfs(j, k);
                        count++;
                    }
                }
            }
            System.out.print(count + " ");
            count = 0;
            check = new boolean[n][n];
            w = true;
        }
    }

    private static void dfs(int x, int y) {
        check[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
                if (!w) {
                    if (selectedColor == map[nowX][nowY] && map[nowX][nowY] == 'R' && !check[nowX][nowY]) {
                        dfs(nowX, nowY);
                    } else if (selectedColor == map[nowX][nowY] && map[nowX][nowY] == 'G' && !check[nowX][nowY]) {
                        dfs(nowX, nowY);
                    } else if (selectedColor == map[nowX][nowY] && map[nowX][nowY] == 'B' && !check[nowX][nowY]) {
                        dfs(nowX, nowY);
                    }
                } else {
                    if ((selectedColor == 'R' || selectedColor == 'G') && (map[nowX][nowY] == 'R' || map[nowX][nowY] == 'G') && !check[nowX][nowY]) {
                        dfs(nowX, nowY);
                    } else if (selectedColor == map[nowX][nowY] && map[nowX][nowY] == 'B' && !check[nowX][nowY]) {
                        dfs(nowX, nowY);
                    }
                }
            }
        }
    }
}