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

이 문제는 적록색약인 사람과 아닌 사람이 봤을 때, 색깔 영역의 갯수를 세는 문제로 전형적인 Flood Fill 문제이다. 따라서, BFS 알고리즘으로 접근하면 문제가 쉬워진다.

그리고, 적록색약인 사람은 R과 G를 구별하지 못해 하나의 색으로 인식하지만, 그렇지 않은 사람은 R과 G를 구별하므로, 먼저 적록색약이 아닌 경우의 답을 구하고, 적록색약인 경우를 구할 때, G를 R로 변경하여 동일한 방식으로 처리하면 된다는 것을 파악할 수 있다. 따라서, Flood Fill을 적용하는 부분은 함수로 빼 두는 것이 코드의 중복을 피할 수 있을 것이다.

코드를 작성해보면 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int n;
char board[100][100];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int flood_fill() {
    queue<pair<int, int>> q;
    bool vis[100][100] = {};
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (vis[i][j]) continue;
            q.push({i, j});
            vis[i][j] = 1;
            cnt++;
            
            while (!q.empty()) {
                int x, y;
                tie(x, y) = q.front();
                q.pop();
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = x + dx[dir], ny = y + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (vis[nx][ny] || board[nx][ny] != board[x][y]) continue;
                    q.push({nx, ny});
                    vis[nx][ny] = 1;
                }
            }
        }
    }
    
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    string buf;
    for (int i = 0; i < n; i++) {
        cin >> buf;
        for (int j = 0; j < n; j++) board[i][j] = buf[j];
    }
    
    // 정상 bfs
    cout << flood_fill() << " ";
    
    // 색약 bfs
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'G') board[i][j] = 'R';
        }
    }
    cout << flood_fill();
}