백준10026번 문제

문제 : 적록색약

문제 설명 : 적록색약인 사람과 정상인의 경우를 나누어 rgb 배열에서 각 색상별 파티션 개수를 구하는 문제. 인접한 색상이 같은 경우 같은 파티션으로 구분한다. 이때 적록색약이 있는 사람의 경우 r 과 g를 구분하지 못하기 때문에 일반인보다 더 적은 파티션 수가 나올 것이다.

코드 :

package Baekjoon;

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

public class Main_10026 {
    static int N;
    static String s;
    static char map[][];
    static boolean visits[][];
    static int dx[] = {-1,0,0,1};
    static int dy[] = {0,1,-1,0};

    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visits = new boolean[N+1][N+1];

        for(int i=0;i<N;i++){
            s = br.readLine();
            for(int j =0;j<N;j++){
                map[i][j] = s.charAt(j);
            }
        }

        // 일반인인 경우
        int cnt =0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visits[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        int normal_cnt = cnt;

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

        // dltonism 인 경우
        // G를 R로 바꿔주고 돌린다.

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j]=='G'){
                    map[i][j] = 'R'; // G를 R로 바꿔준다.
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visits[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        int abnormal_cnt = cnt;
        System.out.println(normal_cnt + " " + abnormal_cnt);

    }
    public static void dfs(int x, int y){
        visits[x][y] = true;
        char tmp_char = map[x][y]; // R
        for(int i=0; i<4; i++){
            int new_x = x+dx[i];
            int new_y = y+dy[i];

            if (new_x<0 || new_y<0 || new_x>=N || new_y>=N){
                continue;
            }

            if (!visits[new_x][new_y] && map[new_x][new_y] == tmp_char){
                dfs(new_x, new_y);
            }
        }
    }
}

문제 풀이: 본 문제는 dfs를 이용한 문제다. dfs를 함수로 만들어 문제를 풀었다. 이때 배열은 총 4개가 필요하고 x,y좌표에서 각 양옆 위아래를 모두 방문하고 방문했다면 visit배열을 +1한다. 이때 중요한 점은 한번 방문하면 다시 방문하지 않는다 즉 한번 방문할때 자신이 속한 파티션을 모두 방문하도록 재귀 호출을 사용한다.

참조 :https://nanchachaa.tistory.com/80