BOJ - 10026 적록색약

10026 번 적록색약

적록색약인 사람과 적록색약이 아닌 사람이 구별할 수 있는 구역의 수를 구하는 문제이다.

bfs를 통해 나누어진 구역의 수를 구할 수 있다.

참고해야 할 사항은 적록색약인 사람은 R과 G를 구분 못하기 때문에 둘을 같은 색으로 여기고 bfs를 적용해야 한다는 점이다.

이런 문제처럼 구역을 나누는 문제에 대해서는 주어진 맵의 모든 구역에 대해 bfs를 적용해야 한다.

문제 해결을 위해 주어진 그림에 대한 정보는 그대로 유지한 채 bfs() 함수로 넘기는 인자에 f(flag)도 같이 넘겨 적록색약일 때와 아닐 때를 구분하여 함수가 적용되도록 하였다.

적록색약이 아닐 때는 그냥 bfs를 적용하였고, 적록색약일 때는 현재 탐색하는 구역의 색이 R,G일 때와 B일 때로 나누어 적용하였다.

코드

#include <iostream>
#include <queue>

using namespace std;

int n;
char arr[101][101];
int visited[101][101]; // 적록색약 x
int visited2[101][101]; // 적록색약 o
int xpos[4] = {1,-1,0,0};
int ypos[4] = {0,0,1,-1};

int bfs(int x, int y, int f)
{
    if(visited[x][y] == 1 && f == 1)
        return 0;
    else if(visited2[x][y] == 1 && f == 2)
        return 0;

    queue<pair<int,int>> q;
    q.push(make_pair(x,y));

    while(!q.empty())
    {
        int a,b;
        a = q.front().first;
        b = q.front().second;
        q.pop();

        if(visited[a][b] == 1 && f == 1)
            continue;
        else if(visited2[a][b] == 1 && f == 2)
            continue;

        if(f == 1)
            visited[a][b] = 1;
        else if(f == 2)
            visited2[a][b] = 1;

        for(int i=0;i<4;i++)
        {
            int ax = a + xpos[i];
            int by = b + ypos[i];

            if(ax < 0 || ax >= n || by < 0 || by >= n)
            {
                if(visited[ax][by] == 1 && f == 1)
                    continue;
                else if(visited2[ax][by] == 1 && f == 2)
                    continue;
            }

            if(arr[a][b] == arr[ax][by] && f == 1)
                q.push(make_pair(ax,by));
            else if(f == 2)
            {
                if((arr[a][b] == 'R' || arr[a][b] == 'G') && (arr[ax][by] == 'R' || arr[ax][by] == 'G'))
                    q.push(make_pair(ax,by));
                else if(arr[a][b] == arr[ax][by])
                    q.push(make_pair(ax,by));
            }
        }
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> arr[i][j];
        }
    }

    /* 적록색약 x*/
    int cnt = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int flag = bfs(i,j,1);

            if(flag == 0)
                continue;
            else
                cnt++;
        }
    }

    /* 적록색약 o*/
    int cnt2 = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int flag = bfs(i,j,2);

            if(flag == 0)
                continue;
            else
                cnt2++;
        }
    }
    cout << cnt << " " << cnt2;

    return 0;
}

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