적록색약 (feat. 백준, 10026번)

적록색약
https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, dx[4], dy[4];
char arr[101][101];
bool visit[101][101];
int bfs1(){     // 적록색약이 아닌 사람
    register int ans = 0;
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            if(!visit[i][j]){
                ++ans;
                q.push(make_pair(i, j));
                visit[i][j] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= N && 1 <= ny && ny <= N && !visit[nx][ny] && arr[i][j] == arr[nx][ny])
                            visit[nx][ny] = true, q.push(make_pair(nx, ny));
                    }
                }
            }
    return ans;
}
int bfs2(){     // 적록색약인 사람
    register int ans = 0;
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            if(!visit[i][j]){
                ++ans;
                q.push(make_pair(i, j));
                visit[i][j] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= N && 1 <= ny && ny <= N && !visit[nx][ny]){
                            if(arr[i][j] == 'B'){
                                if(arr[nx][ny] == 'B')
                                    visit[nx][ny] = true, q.push(make_pair(nx, ny));
                            }
                            else{
                                if(arr[nx][ny] != 'B')
                                    visit[nx][ny] = true, q.push(make_pair(nx, ny));
                            }
                        }
                    }
                }
            }
    return ans;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> N;
    for(register int x = 1, y; x <= N; ++x)
        for(y = 1; y <= N; ++y)
            cin >> arr[x][y];
    cout << bfs1() << " " << bfs2();
    return 0;
}
// *&)*@*

 

반응형

1. 전형적인 너비 우선 탐색 BFS 문제 유형입니다.
2. 적록색약이 아닌 경우, 한 지점을 중심으로 상하좌우가 모두 같은 색인 경우 +1 영역으로 간주됩니다.
3. 적록색약인 경우, 2번과 동일하지만 'R'와 'G'을 동일한 색으로 간주하고 진행하면 됩니다.
4. 이후 2번과 3번에서 구해진 영역의 개수를 각각 출력하면 되겠습니다.