[10026번] 적록색약

문제 출처 :

https://www.acmicpc.net/problem/10026

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS :: http://www.crocus.co.kr/521

BFS를 이용하여 간단하게 해결할 수 있는 문제이다.

적록색약이 아닌 사람(bfs1), 적록색약인 사람(bfs2)을 서로 두고

모든 배열에 방문할 때 까지 아래와 같이 이중 for문으로 둔 후

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++)

            bfs1(i, j);

bfs에서 cnt를 증가시켜주며 총 몇번의 bfs 함수를 들어왔는지 체크하면 모든 map에 대해 방문 횟수를 알 수 있다.

    if (visit1[startY][startX])

        return;

 

    cnt1++;

 

    q.push(pii(startY, startX));

이 코드의 의미는

위의 2중 포문에서 i,j로 들어가는 값이 이전에 방문했던 적이 있는지 체크하는 것이고

방문을 했다면 return;을 방문하지 않았다면 그 구역에 대해 bfs를 돌 예정이므로 cnt1++를 해주고 push를 하는것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
 
queue<pii> q;
 
char map[101][101];
 
bool visit1[101][101];
bool visit2[101][101];
 
int n;
int cnt1, cnt2;
 
// 적록색약이 아닌 사람
void bfs1(int startY, int startX)
{
    if (visit1[startY][startX])
        return;
 
    cnt1++;
 
    q.push(pii(startY, startX));
    
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
 
        q.pop();
 
        if (visit1[y][x])
            continue;
 
        visit1[y][x] = true;
 
        if (y > 0 && map[y - 1][x] == map[y][x])
            q.push(pii(y - 1, x));
 
        if (y < n - 1 && map[y + 1][x] == map[y][x])
            q.push(pii(y + 1, x));
 
        if (x > 0 && map[y][x - 1] == map[y][x])
            q.push(pii(y, x - 1));
 
        if (x < n - 1 && map[y][x + 1] == map[y][x])
            q.push(pii(y, x + 1));
    }
}
 
// 적록색약인 사람
void bfs2(int startY, int startX)
{
    if (visit2[startY][startX])
        return;
 
    cnt2++;
 
    q.push(pii(startY, startX));
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
 
        q.pop();
 
        if (visit2[y][x])
            continue;
 
        visit2[y][x] = true;
        if (y > 0 && (map[y - 1][x] == map[y][x]) || ((map[y - 1][x] == 'R' || map[y - 1][x] == 'G') && (map[y][x] == 'R' || map[y][x] == 'G')))
            q.push(pii(y - 1, x));
 
        if (y < n - 1 && (map[y + 1][x] == map[y][x]) || ((map[y + 1][x] == 'R' || map[y + 1][x] == 'G') && (map[y][x] == 'R' || map[y][x] == 'G')))
            q.push(pii(y + 1, x));
 
        if (x > 0 && (map[y][x - 1] == map[y][x]) || ((map[y][x - 1] == 'R' || map[y][x - 1] == 'G') && (map[y][x] == 'R' || map[y][x] == 'G')))
            q.push(pii(y, x - 1));
 
        if (x < n - 1 && (map[y][x + 1] == map[y][x]) || ((map[y][x + 1] == 'R' || map[y][x + 1] == 'G') && (map[y][x] == 'R' || map[y][x] == 'G')))
            q.push(pii(y, x + 1));
    }
}
 
int main()
{
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%s", map[i]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            bfs1(i, j);
 
    printf("%d ", cnt1);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            bfs2(i, j);
 
    printf("%d", cnt2);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>