[백준 10026] 적록색약

백준 10026 적록색약

이 문제는 DFS 또는 BFS로 풀 수 있는 문제지만 둘 중에 하나로 두 번 돌려야 되는 문제이다. (두가지 풀이로 쓰기 귀찮아서 BFS 풀이만 올리겠다.)

먼저 BFS로 한 바퀴 돌릴 때 G인 곳을 R로 바꾸면서(R을 G로 바꿔도 상관없다) 색상에 의해 몇 구역으로 나뉘는지 체크를 하고 또 다시 BFS로 한 바퀴 돌리면 풀리는 단순한 문제이다.

#include<cstdio>
#include<cstring>
#include<queue>
 
using namespace std;
 
queue<pair<int, int>> q;
 
char map[101][101] = { 0 };
bool visit[101][101] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)scanf("%s", map[i]);
 
    char temp;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!visit[i][j])
            {
                ans++;
                temp = map[i][j];
                visit[i][j] = 1;
                if (temp == 'G')map[i][j] = 'R';
 
                q.push(make_pair(i, j));
                while (!q.empty())
                {
                    pair<int, int> now = q.front(); q.pop();
 
                    for (int k = 0; k < 4; k++)
                    {
                        if (!visit[now.first + dy[k]][now.second + dx[k]] && map[now.first + dy[k]][now.second + dx[k]] == temp)
                        {
                            visit[now.first + dy[k]][now.second + dx[k]] = 1;
                            if (temp == 'G')map[now.first + dy[k]][now.second + dx[k]] = 'R';
                            q.push(make_pair(now.first + dy[k], now.second + dx[k]));
                        }
                    }
                }
            }
        }
    }
 
    printf("%d ", ans);
    ans = 0;
 
    for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)visit[i][j] = 0;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!visit[i][j])
            {
                ans++;
                temp = map[i][j];
                visit[i][j] = 1;
                q.push(make_pair(i, j));
                while (!q.empty())
                {
                    pair<int, int> now = q.front(); q.pop();
 
                    for (int k = 0; k < 4; k++)
                    {
                        if (!visit[now.first + dy[k]][now.second + dx[k]] && map[now.first + dy[k]][now.second + dx[k]] == temp)
                        {
                            visit[now.first + dy[k]][now.second + dx[k]] = 1;
                            q.push(make_pair(now.first + dy[k], now.second + dx[k]));
                        }
                    }
                }
            }
        }
    }
 
    printf("%d ", ans);
    return 0;
}