[BOJ] #10026 적록색약

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

10026번: 적록색약

---

이 문제 또한 백준 #2667 단지 번호 붙이기와 유사한 문제이다. 주어진 행렬 형태의 그래프를 순회하며 같은 문자로 묶인 구역을 탐색하는 문제인데, 이 문제와 다른 문제들의 차별점이라 함은 행렬에서 나타나는 알파벳이 여러가지이고, 그 알파벳들을 각기 다른 구역으로 판별하여 탐색하여야한다. 따라서 기존에 사용하던 BFS 함수 포맷에 char 인자를 하나 더 전달하여 각기 다른 알파벳들을 따로 처리할 수 있도록 해주었다.

이전 문제에서도 그랬지만, 이런 유형의 문제의 핵심은, visited 배열을 얼마나 잘 활용하는가 이다. 어차피 한번 방문했던 구역은 다시는 방문하지 않기때문에 모든 구역에 대해 BFS를 돌린다 해도 상관이 없다. 

문제의 답을 구하기 위한 cnt는, BFS 함수안에서가 아니라 그냥 main문 안에서 처리해 주었으며, 적록색약이 아닌경우와 적록색약인 경우의 케이스를 각각 따로 나누어 적록색인 경우는 입력받은 행렬에서 G를 R로 바꾸어서 탐색하게끔 해주었다. 처음엔 단순하게 따로 행렬을 만들어서 처리하려고 접근하였는데, 생각해보니 그럴 필요가 없었다. 어차피 각각의 케이스마다 따로 visited배열을 초기화 해주어야 하므로, G->R로 바꾸는 작업 역시 겸사겸사 같이 진행해주고 풀었다.

BFS관련 실버문제들에서는 단순히 그래프를 주고 순회하며 진행하는 매커니즘이었다면, 골드문제로 넘어오니깐 조금은 더 세부적인 조건들이 추가되는 것 같다. 당장 #2667 문제도 0과 1만 존재하는 행렬에서 순회하고 탐색하는 문제였다면, 이번 문제는 조건도 3개로 늘었고 케이스 자체도 적록색약인지 아닌지 두가지 경우로 나누어 풀어야 하는 문제이기 때문에 디테일적인 면에서 차이가 나는 편인것 같다.

#include <stdio.h>
#include <queue>

#define MAX 101

using namespace std;

int N;
char arr[MAX][MAX];
bool visited[MAX][MAX] = { false };

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };
            //상  하  좌  우 

void BFS(int x, int y, char c) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX >= 0 && newX < N) && (newY >= 0 && newY < N)
                && visited[newX][newY] == false) {
                if (arr[newX][newY] == c) {
                    Q.push(make_pair(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
    }
}

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

    for (int i=0; i<N; i++)
        scanf("%s", arr[i]);

    int cntR=0, cntG=0, cntB=0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (visited[i][j] == false && arr[i][j] == 'R') {
                BFS(i,j,'R');
                cntR++;
            }
            else if (visited[i][j] == false && arr[i][j] == 'G') {
                BFS(i,j,'G');
                cntG++;
            }
            else if (visited[i][j] == false && arr[i][j] == 'B') {
                BFS(i,j,'B');
                cntB++;
            }
        }
    }

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            visited[i][j] = false;

            if (arr[i][j] == 'G') 
                arr[i][j] = 'R';
        }
    }

    int  cntRR=0, cntBB=0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (visited[i][j] == false && arr[i][j] == 'B') {
                BFS(i,j,'B');
                cntBB++;
            }
            else if (visited[i][j] == false && arr[i][j] == 'R') {
                BFS(i,j,'R');
                cntRR++;
            }
        }
    }

    int total1 = cntR + cntG + cntB;
    int total2 = cntRR + cntBB;
    printf("%d %d\n", total1, total2);

    return 0;
}