(C++) 백준 10026번 - 적록색약

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

10026번: 적록색약

풀이

백준 1926번 그림 문제와 거의 동일한 문제이다.

BFS를 이용하여 풀이를 하였다.

색약이 아닌 사람들은 1926번에서 풀이한 그대로 하면 되고, 색약인 사람들의 경우에만 R과 G를 동일한 색인 것처럼 풀이하면 된다.

//boj 10026 성공
#include <iostream>
#include <queue>
#include <utility>
#define X first 
#define Y second 

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
string brd[102];
int vst_n[102][102];
int vst_c[102][102];
int pic_n; // 일반인이 보는 구역의 수
int pic_c; // 색약인 사람들이 보는 구역의 수
queue<pair<int, int> > Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> brd[i]; // 그림 입력

    for(int i = 0; i < n; ++i){ // 일반인이 보는 구역의 수를 계산
        for(int j = 0; j < n; ++j){
            if(vst_n[i][j] == 0){ // 방문을 안 한 칸이므로 새로운 그림의 시작
                pic_n++; // 그림 수 증가
                Q.push({i, j});
                vst_n[i][j] = 1; // 방문 표시
            }
            while(!Q.empty()){ // 큐가 빌 때까지
                auto cur = Q.front();
                Q.pop();
                for(int k = 0; k < 4; ++k){
                    int nx = cur.X + dx[k];
                    int ny = cur.Y + dy[k];
                    if(nx >= n or ny >= n or nx < 0 or ny < 0) continue; // 범위를 벗어나면 BFS 종료
                    if(vst_n[nx][ny] != 0 or brd[cur.X][cur.Y] != brd[nx][ny]) continue; // 방문을 했던 칸이거나 색이 다르다면 BFS 종료
                    Q.push({nx, ny});
                    vst_n[nx][ny] = 1; // 방문 표시
                }
            }
        }
    }

    for(int i = 0; i < n; ++i){ // 색약인 사람들이 보는 구역의 수를 계산
        for(int j = 0; j < n; ++j){
            if(vst_c[i][j] == 0){ // 방문을 안 한 칸이므로 새로운 그림의 시작 
                pic_c++; // 그림 수 증가
                Q.push({i, j});
                vst_c[i][j] = 1; // 방문 표시
            }
            while(!Q.empty()){ // 큐가 빌 때까지
                auto cur = Q.front();
                Q.pop();
                for(int k = 0; k < 4; ++k){
                    int nx = cur.X + dx[k];
                    int ny = cur.Y + dy[k];
                    if(nx >= n or ny >= n or nx < 0 or ny < 0) continue;  // 범위를 벗어나면 BFS 종료
                    if(vst_c[nx][ny] != 0) continue; // 방문을 했던 칸이면 BFS 종료
                    // 현재 칸이 파랑인데 다음 칸이 빨강이나 녹색이거나 현재 칸이 빨강이나 녹색인데 다음 칸이 파랑이면 BFS 종료
                    if((brd[cur.X][cur.Y] == 'B' and (brd[nx][ny] == 'R' or brd[nx][ny] == 'G')) or ((brd[cur.X][cur.Y] == 'R' or brd[cur.X][cur.Y] == 'G') and brd[nx][ny] == 'B')) continue;
                    Q.push({nx, ny});
                    vst_c[nx][ny] = 1; // 방문 표시
                }
            }
        }
    }
    cout << pic_n << " " << pic_c;
}