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

[문제보기]

 10026. 적록색약

10026번: 적록색약

 

[풀이과정]

BFS 알고리즘을 이용하여 탐색을 통해 구역의 수를 구해주었다. 처음에는 입력값으로 그대로 사용하여 구역의 수를 구하고, 적록색약이 보는 구역의 수를 구해야되기 때문에 초록색(G)를 빨간색(R)로 바꾸어 주고 탐색을 진행했다.

 

[소스코드]

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n, cnt;
char map[100][100] = {0};
bool visit[100][100];
pair<int, int> movdir[4] = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};

void BFS(int a, int b){
    queue<pair<int, int>> q;
    q.push({a, b});

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nexty = y + movdir[i].first;
            int nextx = x + movdir[i].second;

            if(nexty < 0 || n <= nexty || nextx < 0 || n <= nextx) continue;
            if(visit[nexty][nextx] == false) continue;

            if(map[nexty][nextx] == map[y][x]){
                visit[nexty][nextx] = false;
                q.push({nexty, nextx});
            }
        }
    }

}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    cnt = 0;
    memset(visit, true, sizeof(visit));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visit[i][j] == true){
                visit[i][j] = false;
                BFS(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << " ";

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == 'G')
                map[i][j] = 'R';
        }
    }

    cnt = 0;
    memset(visit, true, sizeof(visit));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visit[i][j] == true){
                visit[i][j] = false;
                BFS(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << " ";
}