문제 10026번

풀이 접근

처음에는 int배열이 아닌 char배열을 사용하고, map과 visited배열을 정상인과 적록색인을 따로 따로 만들어 BFS를 통해 풀었지만, 메모리 초과를 받았다. 그래서 하나의 배열로 통일하고 DFS로 바꾸어 풀었다.

1. 색깔이 모여있는 그룹의 개수를 찾는 문제로 완전탐색을 사용하기로 결정했다.
2. 입력된 값을 저장할 map 배열과, 방문 배열을 준비한다.
3. R은 1로 G는 2로 B는 3으로 map 배열에 넣어준다.
4. 2중 for문으로 map을 돌고 추가 for문으로 해당 값을 비교하여 dfs를 돌린다.
5. 적록색약인 사람은 R과 G를 구분하지 못한다고 했으므로 R에 해당했던 1의 값을 2로 바꿔주고 4번 과정에서 k의 시작 값만 2로 올린 다음 dfs를 돌린다.
6. 나온 결과 값을 출력한다.

소스코드

import java.io.*;
public class boj10026 {
    static class Point {
        int x;
        int y;
        char c;
        public Point(int x, int y, char c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        int normal = 0; int sick = 0;
        for (int i = 0; i < N; i++) {
            char[] arr = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                if(arr[j] == 'R'){
                    map[i][j] = 1;
                }else if(arr[j] == 'G'){
                    map[i][j] = 2;
                }else{
                    map[i][j] = 3;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 1; k < 4; k++) {
                    if(!visited[i][j]  && map[i][j] == k){
                        dfs(i,j,k);
                        normal++;
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 1){
                    map[i][j] =2;
                }
            }
        }
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 2; k < 4; k++) {
                    if(!visited[i][j]  && map[i][j] == k){
                        dfs(i,j,k);
                        sick++;
                    }
                }
            }
        }
        System.out.println(normal + " "+ sick);
    }
    public static void dfs(int x, int y, int type){
        visited[x][y] = true;
        for(int[] dir: dirs){
            int nx = x + dir[0];
            int ny = y + dir[1];
            if(nx>=0&&nx<N&&ny>=0&&ny<N && !visited[nx][ny]) {
                if(map[nx][ny] == type){
                    dfs(nx,ny, type);
                }
            }
        }
    }
}

문제핵심

• DFS or BFS