[BOJ]10026 적록색약

• 정상인 / 적록색약인에 대해 구분지을 수 있는 RGB 영역의 개수를 각자 구하는 문제
• DFS / BFS 모두 해결 가능
• sol1: BFS: queue를 사용해 구현
  좀 더 간단히 or 효율적으로 구현할 수 있는듯 싶다.

#include <bits/stdc++.h>
using namespace std;
int N, cntN = 0, cntAb = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char boardN[101][101];
char boardAb[101][101];
bool visitedN[101][101] = {false,};
bool visitedAb[101][101] = {false,};
void bfs(pair<int, int> curpos, int type){
    queue<pair<int, int>> que;
    que.push(curpos);
    if(type == 0) visitedN[curpos.first][curpos.second] = true;
    else if(type == 1) visitedAb[curpos.first][curpos.second] = true;
    while(!que.empty()){
        pair<int, int> cur = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(type == 0){
                if(visitedN[nx][ny] || boardN[cur.first][cur.second] != boardN[nx][ny]) continue;
                visitedN[nx][ny] = true;
            }
            else if(type == 1){
                if(visitedAb[nx][ny] || boardAb[cur.first][cur.second] != boardAb[nx][ny]) continue;
                visitedAb[nx][ny] = true;
            }
            que.push({nx, ny});
        }
    }
}
int main(){
    char tmp;
    cin >> N;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> tmp;
            boardN[i][j] = tmp;
            if(tmp == 'G') tmp = 'R';
            boardAb[i][j] = tmp;
        }
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            //정상인에 대한 탐색
            if(!visitedN[i][j]) {
                ++cntN;
                bfs({i, j}, 0);
            }
            //적녹색약에 대한 탐색
            if(!visitedAb[i][j]){
                ++cntAb;
                bfs({i, j}, 1);
            }
        }
    }
    cout << cntN << ' ' << cntAb;
    return 0;
}

* sol2: DFS

#include <bits/stdc++.h>
using namespace std;
int N, cntN = 0, cntAb = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char boardN[101][101];
char boardAb[101][101];
bool visitedN[101][101] = {false,};
bool visitedAb[101][101] = {false,};
void bfs(pair<int, int> curpos, int type){
    stack<pair<int, int>> stk;
    stk.push(curpos);
    if(type == 0) visitedN[curpos.first][curpos.second] = true;
    else if(type == 1) visitedAb[curpos.first][curpos.second] = true;
    while(!stk.empty()){
        pair<int, int> cur = stk.top();
        stk.pop();
        for(int i = 0; i < 4; ++i){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(type == 0){
                if(visitedN[nx][ny] || boardN[cur.first][cur.second] != boardN[nx][ny]) continue;
                visitedN[nx][ny] = true;
            }
            else if(type == 1){
                if(visitedAb[nx][ny] || boardAb[cur.first][cur.second] != boardAb[nx][ny]) continue;
                visitedAb[nx][ny] = true;
            }
            stk.push({nx, ny});
        }
    }
}
int main(){
    char tmp;
    cin >> N;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> tmp;
            boardN[i][j] = tmp;
            if(tmp == 'G') tmp = 'R';
            boardAb[i][j] = tmp;
        }
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            //정상인에 대한 탐색
            if(!visitedN[i][j]) {
                ++cntN;
                bfs({i, j}, 0);
            }
            //적녹색약에 대한 탐색
            if(!visitedAb[i][j]){
                ++cntAb;
                bfs({i, j}, 1);
            }
        }
    }
    cout << cntN << ' ' << cntAb;
    return 0;
}