[백준 10026] 적록색약

🔗알고리즘 문제

간단한 그래프 탐색으로 해결한 문제이다. 점점 그래프 탐색 문제를 해결하는 실력이 좋아지고 있는 것이 느껴져 보람차다.

문제 분석

이 문제는 R G B로 이루어진 그림 정보가 주어질 때 일반인과 적록색약이 보는 구역의 갯수를 각각 출력하는 문제이다.

발상

적록색약인 경우에서 R과 G를 같은 색으로 생각해야 된다는 것을 빼면 BFS와 DFS를 사용하여 해결할 수 있는 간단한 구역찾기 문제이기 때문에 쉽게 해결할 수 있었다.

나는 나에게 좀 더 익숙한 BFS를 이용하여 문제를 해결하였다.

알고리즘 설계

1. 그림의 정보를 입력받는다.
2. 아직 탐색하지 않은 부분에 대해서 구역을 탐색해준다.
3. 만약 적록색약이라면 R과 G를 같은 구역으로 취급한다.
4. 나눠진 sector의 갯수를 출력한다.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

int n;
vector<string> v;

int destX[4] = { -1, 1, 0, 0 };
int destY[4] = { 0, 0, -1, 1 };

void BFS(int x, int y, bool isWeekness, bool check[101][101]){
    queue<pair<int, int>> q;
    char target = v[y][x];
    
    q.push({ x, y });
    check[y][x] = true;

    while(q.empty() == false){
        pair<int, int> node = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            pair<int, int> next = { node.first + destX[i], node.second + destY[i] };

            if(next.first < 0 || next.first > n - 1 || next.second < 0 || next.second > n - 1)
                continue;
            
            if(check[next.second][next.first] == true)
                continue;

            if(v[next.second][next.first] != target && !(isWeekness && target != 'B' && v[next.second][next.first] != 'B'))
                continue;

            check[next.second][next.first] = true;
            q.push(next);
        }
    }
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        string line;
        cin >> line;
        v.push_back(line);
    }

    int sector = 0;
    bool check[101][101] = {};

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(check[i][j] == false){
                BFS(j, i, false, check);
                ++sector;
            }
        }
    }
    cout << sector << " ";

    sector = 0;
    memset(check, false, sizeof(check));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(check[i][j] == false){
                BFS(j, i, true, check);
                ++sector;
            }
        }
    }
    cout << sector;
}