[BOJ] 10026 적록색약 (G4)

문제

https://www.acmicpc.net/problem/10026

 

풀이

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못하는 것으로 빨간색과 초록색을 같은 색으로 판단한다.

왼쪽의 그림을 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개(R: 2, G: 1, B: 1)이다.

하지만, 적록색약인 사람이 봤을 때, 빨간색과 초록색을 같다고 판단하기 때문에 오른쪽의 그림처럼 총 3개(R/G: 2, B: 1)로 판단한다.

 

이 문제를 풀기 위해서는 적록색약인 경우와 아닌 경우를 구분하여 BFS 탐색을 하도록 풀면 된다.

Code

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static char [][] graph;
    static boolean [][] visited;
    static Queue<int[]> queue;  // x, y로 기입
    static int [] dx = {-1, 1, 0, 0};
    static int [] dy = {0, 0, 1, -1};
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        graph = new char[n][n];
        
        // 입력
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                graph[i][j] = line.charAt(j);
            }
        }
        
        // 적록색약이 아닌 사람이 봤을 때의 구역의 수
        int region = 0;  // 구역 수
        visited = new boolean[n][n];  // 방문 여부
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 방문하지 않은 지역 == 색이 바뀌는 구역의 첫 시작점
                if (!visited[i][j]) {
                    bfs(i, j, false);
                    region++;
                }
            }
        }
        sb.append(region).append(" ");
        
        // 적록색약인 사람이 봤을 때의 구역의 수
        region = 0;
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, true);
                    region++;
                }
            }
        }
        sb.append(region);
        System.out.println(sb);
    }
    
    static void bfs(int x, int y, boolean isBlind) {
        queue = new ArrayDeque<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;  // 방문 처리
        char startColor = graph[x][y];  // 시작 색상
        
        while (!queue.isEmpty()) {
            // 현재 x, y 값
            int [] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            
            // 상하좌우로 다음 값을 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                // 다음 좌표가 범위 내에 있고, 방문하지 않은 경우
                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    // 적록색약인 경우
                    if (isBlind) {
                        if ((startColor == 'R' || startColor == 'G') && (graph[nx][ny] == 'R' || graph[nx][ny] == 'G')) {
                            queue.offer(new int[] {nx, ny});
                            visited[nx][ny] = true;
                        } else if (startColor == 'B' && graph[nx][ny] == 'B') {
                            queue.offer(new int[] {nx, ny});
                            visited[nx][ny] = true;
                        }
                    } else {  // 적록색약이 아닌 경우
                        if (startColor == graph[nx][ny]) {
                            queue.offer(new int[] {nx, ny});
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
    }
}

자동완성 없이 푸는 연습을 하다 보니 작은 실수들이 발생하네요...