[BOJ] 10026 - 적록색약

문제 링크

10026-적록색약

문제 설명

입력

• 그림의 크기
• 그림의 크기에 따른 RGB

출력

• 적록색약이 아닌 사람이 봤을 때의 구역의 수
• 적록색약인 사람이 봤을 때의 구역의 수

문제 풀이

DFS (깊이 우선 탐색) 이용

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

public class Main {

    static int n;
    static int [][]colors;	//그림의 RGB 저장
    static boolean[][] visited;	// 방문했는지 유무
    static int[] dx = {-1,0,1,0};	
    static int[] dy = {0,-1,0,1};

    public static void main(String[] args) throws IOException {
   
   // 처음에는 Scanner 사용했는데 시간초과해서 BufferReader로 수정
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        colors = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                if(tmp[j].equals("R")) colors[i][j] = 1;
                else if(tmp[j].equals("G")) colors[i][j] = 2;
                else if (tmp[j].equals("B")) {
                    colors[i][j] = 3;
                }
            }
        }

// 적록색약이 아닌 사람
        int cnt = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=1; k<4; k++) {
                    if(!visited[i][j] && colors[i][j] == k) {
                        dfs(i,j,k);
                        cnt++;
                    }
                }
            }
        }

// 적색을 녹색과 똑같이 표현
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (colors[i][j] == 1) {
                    colors[i][j] = 2;
                }
            }
        }

// 적록색약인 사람
        int cnt2 = 0;
        visited = new boolean[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=1; k<4; k++) {
                    if(!visited[i][j] && colors[i][j] == k) {
                        dfs(i,j,k);
                        cnt2++;
                    }
                }
            }
        }
        System.out.println(cnt + " " + cnt2);

    }
    
    
    static void dfs(int x, int y, int color) {

        visited[x][y] = true;
        
        // 주변 노드들이 배열의 범위내에 존재하고 방문하지 않았다면 이동
        // 이전의 색과 동일하다면 재귀문 반복
        
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx <0 || ny <0 || nx>n-1 || ny>n-1) continue;
            if(visited[nx][ny]) continue;

            if(colors[nx][ny] == color) {
                dfs(nx,ny, color);
            }
        }

    }
}