10026번: 적록색약

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

10026번: 적록색약

입력받은 2차원 배열의 각 성분을 노드, 인접한 노드 사이의 관계를 에지로 보면, 이 문제는 그래프 탐색을 통해 같은 값을 가진 인접한 노드 집합의 수를 세는 문제이다. 이 때 일반적으로 그래프를 탐색할 경우 visit 배열을 사용해 해당 좌표를 방문했는지 여부를 판단하지만, 주어진 문제에선 그래프를 두 번 탐색해야 하고 그룹을 어느정도 유지해야 하므로, 탐색한 노드의 값을 바꾸는 방법으로 탐색해야 한다.

첫 탐색 때는 값이 'R' 혹은 'G'인 노드의 값을 임의의 값 a로, 값이 'B'인 노드의 값은 임의의 값 b로 탐색하며 이외의 값은 바꾸지 않는다. 그래프 탐색을 한 번 마친 후, 두 번째 탐색에선 값이 'a' 혹은 'b'인 노드의 값을 다른 임의의 값으로 바꾸며 다시 한 번 탐색한다. 이 두 번의 탐색에서 얻은 그룸의 수를 각각 출력하면 된다.

#include <cstdio>

#define MAX_N 100

// 그림을 저장할 공간
char image[MAX_N][MAX_N + 1];
// N: 그림의 한 변의 길이, add: 좌표의 상하좌우 좌표를 계산할 때 사용할 값
int N, add[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

// 좌표 (x, y)가 포함되며 값이 from인 구역을 순회하며 값을 to로 바꾼다
bool dfs(int y, int x, char from, char to) {
    // 좌표 (x, y)와 인접한 좌표를 계산할 때 사용할 변수
    int y_, x_;

    // 현재 좌표의 값을 to로 바꾼 뒤
    image[y][x] = to;
    // 현재 좌표와 인접한 좌표에 대해
    for (auto a : add) {
        // 좌표값을 계산한 뒤
        y_ = y + a[0]; x_ = x + a[1];
        // 좌표가 valid하지 않다면 continue
        if (y_ < 0 || y_ >= N || x_ < 0 || x_ >= N) continue;
        // 해당 좌표의 값이 from이라면 dfs를 통해 방문
        else if (image[y_][x_] == from) dfs(y_, x_, from, to);
    }

    // 편의를 위해 true를 반환
    return true;
}

int main() {
    // RGB: 색약이 아닌 사람이 봤을 때 구역의 수, ab: 색약인 사람이 봤을 때 구역의 수 
    int RGB = 0, ab = 0;

    // 문제의 조건을 입력받은 뒤
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%s", image[i]);

    // 구역을 계산하며 RGB 이미지를 적녹 색약에 맞게 a, b로 바꿔준다 
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (image[i][j] == 'R' || image[i][j] == 'G' || image[i][j] == 'B')
            RGB += dfs(i, j, image[i][j], (image[i][j] == 'B') ? 'b' : 'a');

    // 구역을 계산하며 확인한 좌표를 0으로 초기화
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (image[i][j] == 'a' || image[i][j] == 'b')
            ab += dfs(i, j, image[i][j], 0);

    printf("%d %d\n", RGB, ab);

    return 0;
}