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

백준의 적록색약(10026) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제를 접근하는 방법이 크게 어렵지 않다. 적록색약이 아닌 사람이 봤을 때의 구역의 수는 BFS 함수를 호출하는 횟수와 같을

   것이다.

   1-1) 왜 BFS함수를 호출하는 횟수와 같은가?

  

   맵이 위의 그림와 같이 되어 있다고 생각해보자. 모든 정점에서 BFS함수를 호출하되, 방문하지 않은 정점들에 대해서만 호출을

   해보자. 먼저 (0,0)에 있는(가장 왼쪽 위) R 정점이 호출될 것이다. BFS() 안에서는 자기와 색깔이 같은 'R'인 지점에 대해서만

   Queue에 집어 넣으면서 반복을하게 될 것이고, 아마 (0,0), (0,1), (0,2) 이렇게 3개의 빨간색으로 표시된 R지점이 (0,0)을 호출했을

   때 방문하게 될 것이다.

   다음은 (0,1)을 호출할 것인데, (0,1)은 이미 방문한 지점이기 때문에 넘어갈 것이다.

   그렇다면 다음 호출지점은 (0,3)에 있는 B 정점이 호출될 것이다. 또 저 정점이 호출되면서 모든 B지점을 방문하게 될 것이다.

   이런식으로 호출을 하게 되면, 결국

 

  이렇게 호출될 것이다. 결국 총 4번의 호출을 하게 될 것이고, 이는 적록색약이 아닌 사람이 봤을 때의 구역의 수가 된다.

  적록색약인 사람은 R와 G를 구별하지 못하므로, 본인은 맵에서 R을 G로, 혹은 G를 R로 모두 바꾼 후, 위와 같은 방식으로

  BFS()함수를 호출하는 식으로 구현을 하였다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] == false)
                {
                    if (MAP[nx][ny] == MAP[x][y])
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }
}
void Solution()
{
    int Answer, Answer2;
    Answer = Answer2 = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Visit[i][j] == false)
            {
                BFS(i, j);
                Answer++;
            }
        }
    }
 
    memset(Visit, false, sizeof(Visit));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 'G') MAP[i][j] = 'R';
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Visit[i][j] == false)
            {
                BFS(i, j);
                Answer2++;
            }
        }
    }
 
    cout << Answer << " " << Answer2 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}