[백준 10026] 적록색약 C++

문제

백준 10026 적록색약 C++

10026번: 적록색약

풀이

주어진 조건에 따라 DFS나 BFS를 활용하여 그래프를 탐색해주면 된다.

색약인 경우와 색약이 아닌 경우를 color로 구분하여, 색약이 아닌 경우에는 색깔이 같을 때만 queue에 push해주고

색약인 경우에는 빨강과 초록의 구분이 없게 하여 queue에 push 한다.

소스 코드

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
using namespace std;
 
char map[101][101];
bool visited[101][101];
int N;
// 색맹이 보는 영역
int colorCnt;
// 색맹이 아닌 사람이 보는 영역
int cnt;
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void BFS(int x, int y, bool color)
{
    if (visited[y][x])
        return;
        
    if (color)
        colorCnt++;
    else
        cnt++;
 
    visited[y][x] = true;
    queue<pair<int, int>> q;
    q.push({ x, y });
 
    while (!q.empty())
    {
        int curX = q.front().first;
        int curY = q.front().second;
        char curC = map[curY][curX];
        q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
 
            // 영역을 벗어나지 않고, 방문하지 않은 경우에
            if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && !visited[nextY][nextX])
            {
                char nextC = map[nextY][nextX];
 
                // 색깔이 같은 경우만 queue에 push
                if (nextC == curC || (color == true && curC != 'B' && nextC != 'B'))
                {
                    visited[nextY][nextX] = true;
                    q.push({ nextX, nextY });
                }
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
 
    string input;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        for (int j = 0; j < input.size(); j++)
        {
            map[i][j] = input[j];
        }
    }
 
    // 색맹이 아닌 사람이 보는 영역 세기
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            BFS(j, i, false);
        }
    }
 
    memset(visited, false, sizeof(visited));
 
    // 색맹인 사람이 보는 영역 세기
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            BFS(j, i, true);
        }
    }
 
    cout << cnt << ' ' << colorCnt;
 
    return 0;
}