[백준 10026] 적록색약

문제 링크

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

 

 

문제 분석 

 

R, G, B 총 3가지의 색상이 있고, 각각 구역이 나눠져 있다. 나눠진 구역이 총 몇개인지 세는 문제이다. 

 

여기서 적록색약이 아닌 사람이 봤을땐 R, G, B 모두 나누어져 있지만, 적록색약인 사람이 본다면 R과 G는 하나의 구역으로 생각 하면 된다. 

 

 

알고리즘 설계

이중 vector을 사용하여 판을 구성하고, 입력 받는다. 

 

적록색약이 아닌 사람과 적록색약인 사람이 보는 함수를 따로 만들어준다. 

 

이후 BFS을 사용하여 탐색해준다. 

 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int loop, first = 0, second = 0;
vector<vector<int>> map;
int addX[4] = { 1, -1, 0, 0 };
int addY[4] = { 0, 0, 1, -1 };

void NormalFind();
void SpecialFind();

int main()
{
    string str;
    cin >> loop;

    map.resize(loop);

    for (int i = 0; i < loop; ++i)
    {
        cin >> str;
        for (char c : str)
            map[i].push_back(c);
    }

    NormalFind();
    SpecialFind();

    cout << first << ' ' << second;
}

void NormalFind()
{
    vector<vector<bool>> visited(loop, vector<bool>(loop, false));
    queue<pair<int, int>> q;

    for (int i = 0; i < loop; ++i)
    {
        for (int j = 0; j < loop; ++j)
        {
            if (visited[i][j])
                continue;

            q.push(make_pair(i, j));
            visited[i][j] = true;
            first++;

            while (!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;

                for (int i = 0; i < 4; ++i)
                {
                    int posX = x + addX[i];
                    int posY = y + addY[i];
                    if (posX < 0 || posY < 0 || posX >= loop || posY >= loop)
                        continue;
                    else if (visited[posX][posY])
                        continue;

                    if (map[x][y] == map[posX][posY])
                    {
                        visited[posX][posY] = true;
                        q.push(make_pair(posX, posY));
                    }
                }
                q.pop();
            }
        }
    }
}

void SpecialFind()
{
    vector<vector<bool>> visited(loop, vector<bool>(loop, false));
    queue<pair<int, int>> q;

    for (int i = 0; i < loop; ++i)
    {
        for (int j = 0; j < loop; ++j)
        {
            if (visited[i][j])
                continue;

            q.push(make_pair(i, j));
            visited[i][j] = true;
            second++;

            while (!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;

                for (int i = 0; i < 4; ++i)
                {
                    int posX = x + addX[i];
                    int posY = y + addY[i];
                    if (posX < 0 || posY < 0 || posX >= loop || posY >= loop)
                        continue;
                    else if (visited[posX][posY])
                        continue;

                    if (map[x][y] == map[posX][posY] || (map[x][y] == 'R' && map[posX][posY] == 'G') || (map[x][y] == 'G' && map[posX][posY] == 'R'))
                    {
                        visited[posX][posY] = true;
                        q.push(make_pair(posX, posY));
                    }
                }
                q.pop();
            }
        }
    }
}