백준10026_적록색약 (java)

https://www.acmicpc.net/problem/10026

10026번: 적록색약

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

문제 풀이 방식

• 길찾기 문제처럼 첫 (0,0)부터 방문체크를 하면서 같은 상하좌우에서 같은 색깔이 하나라도 있으면 같은 구역으로 본다. 요소 수 찾기 문제랑 비슷했다.
• 적록색약이 아닌 사람이 보는 구역의 수는 DFS함수를 돌며 색깔이 같을동안 탐색해준다. 색상이 다르면 함수를 종료하고 count+1해준다.
• 그렇다면 적록색약이 아닌사람은?...
• 처음에 그리드의 값을 받을 때 G값을 R로 변경해주면 되지 않을까??
• 그래도 잘 모르겠으니 블로그 검색!
• 찾아보니 나처럼 생각한 사람도 있고, 아예 색약인 사람과 색약이 아닌 사람의 dfs를 따로 만들어줘서 푼사람도 있었다. 나는 visited배열을 하나만 사용해서 중간에 Arrays.fill을 사용해 초기화 후 다시 사용했고, 또 어떤 사람은 visited배열도 2개 따로 만들어 준 사람도 있었다.
• 문제는 어렵지 않았으나, 아직 dfs와 bfs가 익숙하지 않아서 구현하는데 조금 어려웠다.

주의할 점

• 자바에선 배열을 어떻게 초기화 하는지 찾아보다가 Arryas.fill을 찾았고 아무 생각없이 적용했다가 java.lang.ArrayStoreException에러가 났다.
• 찾아보니 2차원 배열에 값을 채우기 위해서는 for each문으로 1차? 배열을 잡아주고 fill해줘야했다.

for(boolean a[] : visited) {
	Arrays.fill(a, false);
}

풀이

public class Main {
    static char[][] grid;
    static int n;
    static int[] dy = {-1, 0, 1, 0}; // 상 좌 하 우
    static int[] dx = {0, -1, 0, 1};
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        grid = new char[n][n];
        visited = new boolean[n][n];

        for(int i=0; i<n; i++) { // 색그리드 생성
            String str = br.readLine();
            grid[i] = str.toCharArray();
        }

        int count = 0, rgcount = 0;

//      적록색약이 아닌 사람
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(!visited[i][j]) {
                    dfs(i, j, grid[i][j]);
                    count++;
                }
            }
        }

        for(boolean a[] : visited) Arrays.fill(a, false);

        for(int i=0; i<n; i++) { // 색약 그리드 생성
            for(int j=0; j<n; j++) {
                if(grid[i][j] == 'G') grid[i][j] = 'R';
            }
        }

//      적록색약인 사람
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(!visited[i][j]) {
                    dfs(i, j, grid[i][j]);
                    rgcount++;
                }
            }
        }
        System.out.println(count + " " + rgcount);
    }

    static void dfs(int y, int x, char color) {
        visited[y][x] = true;

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

            if(valCheck(nextY, nextX) == false) { // 탐색불가능하면...
                continue;
            }

            char nextColor = grid[nextY][nextX];
            if(nextColor == color) {
                visited[nextY][nextX] = true;
                dfs(nextY, nextX, nextColor);
            }
        }
    }

    static boolean valCheck(int y, int x) {
        // 탐색 했던 곳이거나 범위 밖이면 false 탐색가능하면 true;
        if(y >=0 && y < n && x >=0 && x < n && !visited[y][x]) return true;
        return false;
    }
}