[BOJ 10026] 적록색약 C++

난이도: Gold 5
번호: 10026
생성일: March 19, 2023 3:09 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

C++

// BOJ 10026 적록색약
#include <iostream>
#include <queue>
using namespace std;

int N;
char map[102][102];
bool visit[102][102];

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

bool _strchr(string s, char c)
{
    for (char _c : s)
        if (c == _c)
            return (1);
    return (0);
}

int BFS(int i, int j, string colors)
{
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visit[i][j] = true;

    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = dx[k] + cur.first;
            int y = dy[k] + cur.second;

            if (visit[x][y])
                continue;

            if (!_strchr(colors, map[x][y]))
                continue;

            Q.push({x, y});
            visit[x][y] = true;
        }
    }
    return (1);
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    // normal, color-weak
    int nm = 0, cw = 0;
    cin >> N;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> map[i][j];

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            if (visit[i][j])
                continue;
            if (map[i][j] == 'R')
                nm += BFS(i, j, "R");
            else if (map[i][j] == 'G')
                nm += BFS(i, j, "G");
            else if (map[i][j] == 'B')
                nm += BFS(i, j, "B");
        }

    // reset visit
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            visit[i][j] = false;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            if (visit[i][j])
                continue;
            if (map[i][j] == 'R' || map[i][j] == 'G')
                cw += BFS(i, j, "RG");
            else if (map[i][j] == 'B')
                cw += BFS(i, j, "B");
        }
    cout << nm << " " << cw;
}