[10026] 적록색약

문제 링크 : https://www.acmicpc.net/problem/10026

10026 - 적록색약

본문

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

첫째 줄에 $N$이 주어진다. ($1 \leq N \leq 100$)

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

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

• $1 \leq N \leq 100$

---

풀이

그래프 탐색 문제 중 일반적인 유형의 문제 중 하나인 영역 구하기 문제이다. 같은 문자로 이루어진 영역은 모두 같은 하나의 영역으로 묶는 문제를 풀듯이 풀면 된다.

기본적인 문제와 다른 점은, 적록색약이 걸린 사람에게는 “빨간색과 초록색의 구분이 없어진다”는 점일 것이다. 이것을 구현할 때는 몇가지 선택을 할 수 있다.

• grid의 내용을 바꾼다. 예를 들어 빨간색과 초록색의 구분이 없어지므로 모든 초록색을 빨간색으로 바꾼 다음 영역의 수를 계산하는 것이다
• 탐색을 진행하는 중에 두 색을 같은 색이라고 강제로 집어넣는다. grid를 수정하지 않아도 된다는 장점이 있다

이 문제를 해결할 때, 그래프 탐색은 dfs, 색깔을 합치는 것은 후자의 방법으로 진행하였다. blind 변수를 매개변수로 전달해주어, 만약 이것이 true라면 빨간색과 초록색을 같은 색으로 보도록 조절하였다.

• 참고 알고리즘 : DFS 탐색

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 31

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
    int x, y;
} ND;

#define RED 'R'
#define BLUE 'B'
#define GREEN 'G'

#define MAX_IDX 100
char grid[MAX_IDX][MAX_IDX + 1];
bool visit[MAX_IDX][MAX_IDX] = {false};
int n;
ND dir[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void init() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            visit[i][j] = false;
        }
    }
    return;
}

void wrap(int x, int y, int mark, bool blind) {
    for (int i = 0; i < 4; ++i) {
        ND cur = (ND){x + dir[i].x, y + dir[i].y};
        if (0 <= cur.x && cur.x < n && 0 <= cur.y && cur.y < n && visit[cur.x][cur.y] == false) {
            if (grid[cur.x][cur.y] == mark || (blind == true && grid[cur.x][cur.y] + mark == RED + GREEN)) {
                visit[cur.x][cur.y] = true;
                wrap(cur.x, cur.y, mark, blind);
            }
        }
    }
    return;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", grid[i]);
    }

    int retval = 0;
    init();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (visit[i][j] == false) {
                visit[i][j] = true;
                ++retval;
                wrap(i, j, grid[i][j], false);
            }
        }
    }
    printf("%d ", retval);

    retval = 0;
    init();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (visit[i][j] == false) {
                visit[i][j] = true;
                ++retval;
                wrap(i, j, grid[i][j], true);
            }
        }
    }
    printf("%d", retval);

    return 0;
}

• grid[][] : 입력으로 주어지는 맵을 기록
• visit[][] : dfs 탐색을 위한 visit배열
• blind : dfs 탐색 중, 빨간색과 초록색을 같은 색으로 볼 것인지 나타내는 파라미터