[Gold V] 적록색약 - 10026

문제 링크

성능 요약

메모리: 20212 KB, 시간: 220 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 15일 22:32:41

문제 설명

<p>적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.</p>

<p>크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)</p>

<p>예를 들어, 그림이 아래와 같은 경우에</p>

<pre>RRRBB GGBBB BBBRR BBRRR RRRRR</pre>

<p>적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)</p>

<p>그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.</p>

입력

<p>첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)</p>

<p>둘째 줄부터 N개 줄에는 그림이 주어진다.</p>

출력

<p>적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.</p>

풀이

java코드 복사
import java.util.*;
 
public class Main {
 
    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 args[]) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new char[n+1][n+1];
        visits = new boolean[n+1][n+1];
 
        for (int i=0; i<n; i++){
            s= sc.next(); // RRRBB
            for (int j=0; j<n; j++){
                map[i][j]= s.charAt(j); // R R R B B
            }
        }
 
        // normal 인 경우
        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 인 경우
        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);
            }
        }
    }
    
}