白俊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座標では各左右上下にアクセスし,アクセスした場合は+1にアクセスする.この場合、重要なのは、1回のアクセスでアクセスがなくなり、1回のアクセスで再帰コールを使用してすべてのパーティションにアクセスすることです。