BOJ_G5_10026

📁 [G5_10026] 적록색약

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

public class Main {
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0,};
    static char[][] arr;
    static int N;
    static boolean[][] v;
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 크기
        N = Integer.parseInt(br.readLine());

        // 입력
        arr = new char[N+1][N+1];
        v = new boolean[N+1][N+1];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        // 기본

        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!v[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        sb.append(cnt).append(" ");

        // 색맹

        cnt = 0;
        v = new boolean[N+1][N+1];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(arr[i][j] == 'G'){
                    arr[i][j] = 'R';
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!v[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        sb.append(cnt);

        System.out.println(sb);
    }


    static void dfs(int x, int y) {
        v[x][y] = true;
        char num = arr[x][y];


        for (int z = 0; z < 4; z++) {
            int nx = x + dx[z];
            int ny = y + dy[z];

            if (nx < 0 || ny < 0 || nx > N || ny > N) {
                continue;
            }
            else if (!v[nx][ny] && arr[nx][ny] == num) {
                dfs(nx, ny);
            }
        }
    }
}

🤔 나의 생각

dfs와 방향탐색을 합하여 구현하였다.
먼저 적록색약이 아닌 사람이 봤을 때의 구역의 개수는 처음 위치 부터 4방향 탐색을 하며 dfs() 알고리즘을 수행하면 구역들이 나온다.
그 구역을 카운팅 해주고 전체 카운팅을 구해주면 된다.
다음 적록색약이 있는 사람이 봤을 때는 G를 R로 바꿔주고 똑같은 방식으로 구현하면 된다.
dfs와 방향탐색을 구현할 줄 안다면 어렵지 않은 문제였다.