BOJ 10026 - 적록색약 | 방과후 블로그

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

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

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

출력

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

풀이

영역의 개수를 세는 문제이므로, 아직 방문하지 않은 칸에서 BFS나 DFS를 시작해 같은 색 영역을 한 번에 지우는 방식이 자연스럽다. 정상 시야와 적록색약 시야는 색을 구분하는 기준만 다르다.

코드에서는 정상 기준과 적록색약 기준으로 두 번 영역 수를 센다. 적록색약일 때는 R과 G를 같은 색으로 취급하면 된다.

같은 영역 세기 문제를 색 비교 기준만 바꿔 두 번 수행하는 구조다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int N;
    static char[][] graph;
    static boolean[][] visitedA, visitedB;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new char[N][N];
 
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++)
                graph[i][j] = input.charAt(j);
        }
 
        solve();
 
        System.out.println(sb);
    }
 
    static void solve() {
        int cntA = 0, cntB = 0;
        visitedA = new boolean[N][N];
        visitedB = new boolean[N][N];
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visitedA[i][j]) {
                    cntA++;
                    checkArea(i, j, false);
                }
 
                if (!visitedB[i][j]) {
                    cntB++;
                    checkArea(i, j, true);
                }
            }
        }
 
        sb.append(cntA).append(" ").append(cntB);
    }
 
    static void checkArea(int x, int y, boolean isBlindness) {
        char curColor = graph[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if (isBlindness) {
                    if (!visitedB[nx][ny] && checkRG(graph[nx][ny], curColor)) {
                        visitedB[nx][ny] = true;
                        checkArea(nx, ny, true);
                    }
                } else {
                    if (!visitedA[nx][ny] && graph[nx][ny] == curColor) {
                        visitedA[nx][ny] = true;
                        checkArea(nx, ny, false);
                    }
                }
            }
        }
    }
 
    static boolean checkRG(char next, char cur) {
        if (next == 'B')
            return next == cur;
        else
            return cur != 'B';
    }
}

복잡도

시간 복잡도: $O(N^2)$
공간 복잡도: $O(N^2)$

마무리

문제는 복잡해 보여도 결국 영역 개수를 두 번 세는 것이다. 정상 시야와 적록색약 시야의 색 비교 기준만 다르게 두면 된다.

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리