[백준] 10026. 적록색약 (C++)

백준 10026. 적록색약 (Gold V)

Type: dfs

 

문제

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

 

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

 

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

 

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

 

입력

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

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

 

출력

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

 

예제 입력 및 예제 출력

 

풀이

이번에도 그래프 문제를 풀어보았다. 일단 계획상으로는 한 유형을 10개씩 연달아 풀어보고, 그다음에 다른 유형으로 넘어가려 한다.

 

이번에는 Gold V 등급 문제를 풀어보았는데, 생각보다 그렇게 어렵지는 않았다. 하지만 코딩 실수 때문에 시간이 너무 오래 걸렸었다 8-8,,,

Silver 등급까지는 단순한 경로 탐색 문제들이 많아서 각 픽셀의 값이 0 또는 1이었는데, 이번 문제는 R, G, B 세 가지의 값을 가지며, 적록 색약일 경우에는 R과 G를 묶어줘야 한다는 조건도 추가되어있다.

 

하지만, dfs 원리에 입각하여 풀면 쉽게 풀 수 있는데, 인접한 구역의 개수를 count 한다는 점에서 1012. 유기농 배추 풀이 문제와 유사하다. 이 문제는 다음 2가지에 신경을 써줘야 한다.

 

1. 0과 1이 아닌 R, G, B 세 가지의 값을 가진다는 점

2. 적록 색약일 경우에는 R과 G가 하나의 구역이 된다는 점

 

앞서 말했듯이, 유기농 배추 풀이 문제와 비슷한데 이번에는 배추 구역의 수를 count 하는 것이 아니라, 색 구역의 수를 count하는 것이다. 이때 dfs를 이용해 인접한 픽셀의 값이 내 색상과 같다면 방문처리를 해주어, 탐색하고자 하는 픽셀이 이미 방문한 구역인지를 확인해주면 된다.

여기서 적록색약일 경우에는 내 색상이 R일 경우, R 뿐만 아니라 G도 같은 구역으로 인지하며 그 반대도 (내 색상이 G일 경우) 동일하다.

 

따라서 위 내용을 기반으로 다음과 같이 코드를 구현해준다.

 

1. 색상 위치 기록

테스트 케이스가 문자열로 입력되므로, 문자열 입력 함수를 이용해 배열에 저장해준다. 따라서 각 배열의 인덱스에 접근하면 해당 픽셀의 값에 접근할 수 있다.

 

2. 색상 전수 조사

전체 행렬 칸을 전수 조사하여 만약 방문하지 않은 곳이라면, dfs를 통해 해당 칸 및 주변에 같은 색상이 있는지 조사해준다.

 

3. 주변으로 이동

주변에 같은 색상이 있는지 조사하기 위해 동, 서, 남, 북으로 움직인다. 이때 동, 서, 남, 북은 2차원 배열의 관점에서 다음과 같이 표현될 수 있다.

 

동 : (0, 1)

서 : (0, -1)

남 : (1, 0)

북 : (-1, 0)

 

따라서 for문을 이용해 동, 서, 남, 북으로 (총 4차례) 이동한 좌표를 계산해준다.

 

4. 다음 이동위치 범위 체크

만약 다음으로 이동할 곳이 범위에 벗어난다면, 해당 회차를 건너뛰고, 그다음 위치를 체크해준다.

 

5. 적록 색약인 경우

코드 라인 수를 줄이기 위해 color_blind 변수를 이용해 적록 색약인 경우에 대한 조건문을 작성해주었다. 적록 색약일 경우에는 다음과 같이 동작한다.

 

5-1) 현재 픽셀의 색상이 B인 경우

인접한 픽셀의 색상이 B인 경우에만 해당 위치로 이동한다.

 

5-2) 현재 픽셀의 색상이 R 또는 G인 경우

인접한 픽셀의 색상이 R 또는 G면 해당 위치로 이동한다.

 

6. 적록 색약이 아닌 경우

인접한 픽셀의 색상이 현재 픽셀의 색상과 같은 경우에만 해당 위치로 이동한다.

 

/*
* Author : Kwangrok Baek (zester926@gmail.com)
* memory, time : 2148 KB, 0ms
* URL : https://www.acmicpc.net/problem/10026
* type : dfs
*/

#include <iostream>
#include <cstring>

using namespace std;

int n, i, j, block_count;
char arr[101][101];
bool check[101][101];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

bool dfs(int y, int x, bool color_blind) {
    if (check[y][x]) return false;
    check[y][x] = true;
    
    for (int k = 0; k < 4; k++) {
        int next_x = x + dx[k]; // 3. 동, 서, 남, 북으로 1칸씩 이동 
        int next_y = y + dy[k];

        if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= n || check[next_y][next_x]) continue; // 4. 범위 벗어날 시, 패스

        if (color_blind) { // 5. 적록 색약일 경우
            if ((arr[y][x] == 'B' && arr[next_y][next_x] == arr[y][x]) || \
                ((arr[y][x] == 'R' || arr[y][x] == 'G') && (arr[next_y][next_x] == 'R' || arr[next_y][next_x] == 'G'))) { // 6. 파란색일 경우와 적색, 초록색일 경우를 나눠 dfs 다르게 수행
                 dfs(next_y, next_x, true);
            }
        }
        else {
            if (arr[next_y][next_x] == arr[y][x]) { // 7. 적록 색약이 아닐 경우, 본인의 색에 대해서만 dfs 수행
                dfs(next_y, next_x, false);
            }
        }

    }
    return true;
}

int main(void) {
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%s", arr[i]); // 1. 문자열 입력
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (!check[i][j] && dfs(i, j, false)) block_count++; // 2. 탐색 안한 구역일 경우, dfs 수행 & count 추가
        }
    }
    printf("%d ", block_count);

    memset(check, 0, sizeof(check));
    block_count = 0;

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (!check[i][j] && dfs(i, j, true)) block_count++;
        }
    }
    printf("%d", block_count);
}

 

zester926/Algorithm-challenge