[Algorithm Study] 백준 10026

SeokHwan An·2022년 3월 27일
0

문제 출처 : https://www.acmicpc.net/problem/10026

문제 접근

위의 문제를 보면 알 수 있듯이 적록색약은 빨간색과 초록색을 구분하지 못하는 것입니다. 즉 적록색약이 아닌 사람의 경우 R, G, B의 영역을 구하면 되는 것이고 적록색약인 경우에는 B, R&G의 영역을 구하면 됩니다. 이는 DFS를 활용하여 문제를 해결했습니다.

소스 코드

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

public class Main {
    static int N;
    static char[][] map1;
    static char[][] map2;
    static int cnt1;
    static int cnt2;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map1 = new char[N][N];
        map2 = new char[N][N];
        cnt1 = 0;
        cnt2 = 0;
        for(int i = 0 ; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map1[i][j] = str.charAt(j);
                map2[i][j] = str.charAt(j);
            }
        }
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map1[i][j] == 'R') {
                    R(i, j);
                    cnt1++;
                }
                if (map1[i][j] == 'G'){
                    G(i, j);
                    cnt1++;
                }
                if (map1[i][j] == 'B') {
                    B(i, j);
                    cnt1++;
                }
                if (map2[i][j] == 'R' || map2[i][j] == 'G'){
                    R_G(i, j);
                    cnt2++;
                }
                if (map2[i][j] == 'B'){
                    B2(i, j);
                    cnt2++;
                }
            }
        }
        System.out.println(cnt1+" "+cnt2);
    }
    public static void R(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N){
            return;
        }
        if(map1[x][y] == 'R'){
            map1[x][y] = 'C';
            R(x-1,y);
            R(x+1,y);
            R(x,y-1);
            R(x,y+1);
        }
    }
    public static void B(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N){
            return;
        }
        if(map1[x][y] == 'B'){
            map1[x][y] = 'C';
            B(x-1,y);
            B(x+1,y);
            B(x,y-1);
            B(x,y+1);
        }
    }
    public static void G(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N){
            return;
        }
        if(map1[x][y] == 'G'){
            map1[x][y] = 'C';
            G(x-1,y);
            G(x+1,y);
            G(x,y-1);
            G(x,y+1);
        }
    }
    public static void R_G(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N){
            return;
        }
        if(map2[x][y] == 'R' || map2[x][y] == 'G'){
            map2[x][y] = 'C';
            R_G(x-1,y);
            R_G(x+1,y);
            R_G(x,y-1);
            R_G(x,y+1);
        }
    }
    public static void B2(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N){
            return;
        }
        if(map2[x][y] == 'B'){
            map2[x][y] = 'C';
            B2(x-1,y);
            B2(x+1,y);
            B2(x,y-1);
            B2(x,y+1);
        }
    }
}

0개의 댓글