[BOJ] 10026 - 적록색약

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/10026

10026번: 적록색약

난이도: 골드 5

사용 언어: JAVA

 

적록색약은 빨간색과 초록색을 구별하지 못합니다. 그래서 적록색약인 사람이 그림을 보면 일반인이 보는 것과는 조금 다를 수 있습니다. NxN 크기의 그림에 빨강, 초록, 파랑 세 가지 색을 이용해 색칠이 되어 있습니다. 그리고 이 색깔들에 의해 구역이 나누어져 있습니다.

 

같은 색깔들끼리 뭉쳐있으면, 이를 한 구역으로 간주하고, 뭉쳐있다는 것은, 같은 색깔들이 각각의 상하좌우에 존재한다는 뜻입니다. 아래의 예시를 보겠습니다.

 

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

 

일반인들이 보기에 위의 예시에는 4개의 구역이 존재합니다. 하지만 적록색약인 사람이 이를 보면 빨간색과 초록색을 구별할 수 없기 때문에 다음과 같이 보일 것입니다. 

 

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

 

따라서 적록색약에게는 위의 예시는 3가지 구역으로만 이루어진 그림입니다. 이런 식으로 그림이 주어졌을 때, 일반인과 적록색약이 몇 개의 구역으로 구별을 할 수 있는지를 구하는 문제입니다.

 

풀이

이 문제는 dfs나 bfs를 사용하면 해결할 수 있는 문제입니다. 저는 dfs를 이용하여 해결하였고, 다른 문제들과 조금 다른 점이라면, 일반인과 적록색약, 두 케이스를 모두 구해야 하기 때문에, 배열도 두 개, dfs 함수도 두 개를 만들어서 구현했다는 점입니다.  DFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

 

먼저 입력으로부터, 일반인이 보는 시점과, 적록색약이 보는 시점을 따로 배열을 만들어 넣었습니다. 일반인을 위한 배열은 그냥 입력 그대로 받고, 적록색약을 위한 배열은 G가 나오면 대신 R을 집어넣는 방식으로 R과 G의 구분을 없앴습니다.

 

그 뒤부터는 다른 dfs 문제들과 동일하게, 반복문을 돌며 dfs로 구역을 탐지했습니다. 그리고 한 번 탐지한 곳은 다시 탐지하지 않도록 0으로 바꿔주면서 진행했습니다.

 

다른 dfs 문제들과 크게 다른 부분이 없기 때문에 그림을 이용한 설명은 생략하도록 하겠습니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Main {
 
    static int normal_count = 0;
    static int rg_count = 0;
    static int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 인접한 4개의 방향을 배열로 표현
    static int N;
 
    public static void dfs_normal(int x, int y, char arr[][], char color) { // 일반인을 위한 dfs
        int i;
        for (i = 0; i < 4; i++) { // 한 지점의 상하좌우를 검사
            if (x + d[i][0] >= 0 && x + d[i][0] < N && y + d[i][1] >= 0 && y + d[i][1] < N) { // 배열의 크기를 벗어나지 않도록 검사를 진행
                if (arr[x + d[i][0]][y + d[i][1]] != '0' && arr[x + d[i][0]][y + d[i][1]] == color) { // 해당 칸이 0이 아니고, 색깔이 같으면,
                    arr[x + d[i][0]][y + d[i][1]] = '0'; // 중복 검사를 막기 위해 0으로 바꿔주고,
                    dfs_normal(x + d[i][0], y + d[i][1], arr, color); // dfs 수행
                }
            }
        }
    }
 
    public static void dfs_rg(int x, int y, char arr[][], char color) { // 적록색약을 위한 dfs. 함수는 dfs_normal과 동일
        int i;
        for (i = 0; i < 4; i++) {
            if (x + d[i][0] >= 0 && x + d[i][0] < N && y + d[i][1] >= 0 && y + d[i][1] < N) {
                if (arr[x + d[i][0]][y + d[i][1]] != '0' && arr[x + d[i][0]][y + d[i][1]] == color) {
                    arr[x + d[i][0]][y + d[i][1]] = '0';
                    dfs_normal(x + d[i][0], y + d[i][1], arr, color);
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int i, j;
        char[][] arr1 = new char[N][N]; // 일반인을 위한 배열
        char[][] arr2 = new char[N][N]; // 적록색약을 위한 배열
        String s;
 
        for (i = 0; i < N; i++) {
            s = br.readLine();
            for (j = 0; j < N; j++) {
                arr1[i][j] = s.charAt(j);
                if (arr1[i][j] == 'G') // 적록색약을 위한 배열에는 G를 모두 R로 변경해서 저장
                    arr2[i][j] = 'R';
                else
                    arr2[i][j] = s.charAt(j);
            }
        }
 
        char color;
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if (arr1[i][j] != '0') {
                    color = arr1[i][j];
                    arr1[i][j] = '0';
                    dfs_normal(i, j, arr1, color);
                    normal_count++;
                }
                if (arr2[i][j] != '0') {
                    color = arr2[i][j];
                    arr2[i][j] = '0';
                    dfs_rg(i, j, arr2, color);
                    rg_count++;
                }
            }
        }
        System.out.println(normal_count + " " + rg_count);
    }
}