[JAVA]백준10026번 적록색약

문제는 다음과 같다.

오늘은 백준10026번 적록색약 문제를 풀어보도록 하자. JAVA에 익숙해지기 위해서 푼 기본적인 BFS or DFS문제이다.

적록색약이 아닌 사람과 적록색약인 사람이 보는 그룹의 갯수를 구하는 문제였다. BFS로 풀 수도 있고 DFS로 풀 수도 있는 문제였다. 본인은 DFS로 풀이를 하겠다.

1) 적록색약이 아닌 사람 –> 적록색약이 아닌 사람은 R,G,B를 모두 구별할 수 있다. 따라서 main함수에서 방문처리가 되지 않았으면 DFS함수를 실행을 하고 DFS함수에서 방문처리를 할 수 있게 로직을 짰다.

2) 적록색약인 사람 –> 적록색약인 사람은 R,G를 구별못하고 B를 구별할 수 있다. 따라서 적록색약이 아닌 사람의 함수와 같이 방문처리를 하되, 현재 위치가 R or G이고 다음 위치가 R or G이면 재귀함수를 호출하는 형식으로 로직을 짰다. 그리고 현재 위치가 B라면 다음 위치도 B여야 한다.

                                     [코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N,Can_answer=0,Cant_answer=0;
    static boolean visit[][];
    static char map[][];
    static int dir[][] = { {-1,0},{0,1},{1,0},{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 char[N][N];
        visit = new boolean[N][N];

        for(int i=0;i<N;i++){
            String s = br.readLine();
            map[i] = s.toCharArray();
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]){
                    Can_coLor(i,j);
                    Can_answer++;
                }
            }
        }
        System.out.printf(Can_answer + " ");
        for(int i=0;i<N;i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = false;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]){
                    Cant_coLor(i,j);
                    Cant_answer++;
                }
            }
        }
        System.out.println(Cant_answer);
    }
    public static void Can_coLor(int y, int x){
        visit[y][x] = true;
        for(int i=0;i<4;i++){
            int my = y+dir[i][0];
            int mx = x+dir[i][1];

            if(my>=0&&mx>=0&&my<N&&mx<N){
                if(!visit[my][mx]){
                    if(map[y][x] == map[my][mx]){
                        visit[my][mx] = true;
                        Can_coLor(my,mx);
                    }
                }
            }
        }
    }
    public static void Cant_coLor(int y, int x){
        visit[y][x] = true;
        for(int i=0;i<4;i++){
            int my = y+dir[i][0];
            int mx = x+dir[i][1];

            if(my>=0&&mx>=0&&my<N&&mx<N){
                if(!visit[my][mx]){
                    if(map[y][x] == 'R' || map[y][x] == 'G'){
                        if(map[my][mx] == 'R' || map[my][mx] =='G'){
                            visit[my][mx] = true;
                            Cant_coLor(my,mx);
                        }
                    }
                    else{
                        if(map[y][x] == map[my][mx]){
                            visit[my][mx] = true;
                            Cant_coLor(my,mx);
                        }
                    }
                }
            }
        }
    }
}