백준 : 10026번 적록색약 BFS(c++)

백준 링크

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

10026번: 적록색약

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	51980	29874	22850	56.481%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

코드 풀이

BFS를 활용하여 풀이하였습니다.

이번 문제는 기본적인 BFS를 활용한 같은 공간의 개수를 구하는 방법인데 약간 다른 부분은 적록색약의 탐색을 한번 더 추가로 해줘야 한다는것입니다.

그래서 기본 색상을 담은 벡터와 적록색약이 보이는 색상을 담은 벡터 두가지와 그 두개의 방문노드를 확인할 벡트 두개를 만들어 구현하였습니다.

 

ColorFill함수 설명

ColorFill 함수는 말 그대로 빈공간의 벡터에 색상을 채워 넣는 함수입니다.

Color벡터에는 기본색상, DiffColor에는 적록색약의 색상을 채워넣게 됩니다.

 

BFS함수 설명

구역의 개수를 알아야 하기 때문에 int를 리턴값으로 주었습니다.

1. 리턴하기위한 Count 변수와 경로를 담을 큐 생성

2. 탐색할 구역은 N x N이기 때문에 2중 포문 설정

2.a 전부 탐색을 진행하지만 이미 탐색한 부분은 재탐색 하면 안되기 때문에 Visit[i][j] 는 true가 아닐때만 실행하도록 구현

2.b 큐와 방문벡터에 현재 위치를 넣어주고 Count는 1 증가

(Count를 1 증가하는 이유는 바로 밑에서 진행되는 while문에서 해당 위치에서 갈 수 있는 구역을 전부 탐색하기 때문)

3. 큐가 빌때까지 반복문(BFS 탐색)

3.a 현재의 위치를 얻어와 4가지 방향으로의 탐색을 진행

(단, 예외처리는 필수)

코드

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

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void ColorFill(vector<string>& Color, vector<string>& DiffColor, int N)
{
    for (int i = 0; i < N; ++i)
    {
        string sColor, sDiffColor;
        sColor.resize(N);
        sDiffColor.resize(N);
        for (int j = 0; j < N; ++j)
        {
            cin >> sColor[j];

            sDiffColor[j] = sColor[j];

            if (sDiffColor[j] == 'R')
                sDiffColor[j] = 'G';
        }

        Color[i] = sColor;
        DiffColor[i] = sDiffColor;
    }
}

int BFS(const vector<string>& Color, vector<vector<bool>>& Visit, const int& N)
{
    int Count = 0;

    queue<pair<int, int>> qPos;
   
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (Visit[i][j])
                continue;

            qPos.push({ i, j });
            Visit[i][j] = true;
            ++Count;

            while (!qPos.empty())
            {
                pair<int, int> Cur = qPos.front();
                qPos.pop();

                for (int Dir = 0; Dir < 4; ++Dir)
                {
                    int NextX = Cur.second + dx[Dir];
                    int NextY = Cur.first + dy[Dir];

                    if (NextX < 0 || NextY < 0 || NextX >= N || NextY >= N)
                        continue;

                    if (Color[NextY][NextX] != Color[Cur.first][Cur.second] || Visit[NextY][NextX] == true)
                        continue;

                    qPos.push({ NextY, NextX });
                    Visit[NextY][NextX] = true;
                }
            }
        }
    }
    

    return Count;
}

int main()
{
    vector<string> NormalColor;
    vector<string> DifferentColor;

    int N;

    cin >> N;

    vector<vector<bool>> NormalVisit(N, vector<bool>(N));
    vector<vector<bool>> DiffVisit(N, vector<bool>(N));
    NormalColor.resize(N);
    DifferentColor.resize(N);
    
    ColorFill(NormalColor, DifferentColor, N);

    cout << BFS(NormalColor, NormalVisit, N) << ' ';
    cout << BFS(DifferentColor, DiffVisit, N);

    return 0;
}