[ 프로그래머스 카카오 프렌즈 컬러링북 (Lv2) ] (C++)

프로그래머스의 카카오 프렌즈 컬러링북(Lv2) 문제이다.

[ 문제풀이 ]

1) 본인은 이문제를 너비우선탐색(BFS)를 이용해서 접근해 보았다.

   인접한 영역들끼리 같은 색깔을 가지고 있다면, 방문 체크를 해주면서 탐색을 진행해주었다.

   물론 정답을 찾기 위해서 탐색 하면서 탐색 중인 영역의 크기를 따로 Count 해 주었다.

   영역의 갯수는, BFS함수가 호출되는 횟수와 동일하다.

   예를 들어서

   1 1 0 2

   1 0 0 2

   0 3 3 0

   0 3 3 0

   과 같은 맵이 존재할 때, 영역의 갯수는 3개 인데, (0, 0)에 존재하는 '0'에 의해서 BFS탐색 한번 호출,

   (0, 3)에 있는 '2'에 의해서 BFS탐색 한번 호출, (2, 1)에 있는 '3'에 의해서 BFS탐색 한번 호출

   즉, 총 3번의 BFS함수가 호출되어진다. 즉, BFS함수 호출 횟수가 영역의 갯수가 된다.

[ 소스코드 ]

#include <vector>
#include <queue>
#include<iostream>
using namespace std;
 
int Max_Size;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
bool Visit[100][100];
 
int BFS(int a, int b, int m, int n, vector<vector<int>> MAP)
{
    int Color = MAP[a][b];
    int Size = 1;
    queue<pair<int,int>> Q;
    Q.push(make_pair(a,b));
    Visit[a][b] = true;
    
    while(Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        
        for(int i = 0 ; i < 4; i++)
        {
            int nx = x +dx[i];
            int ny = y+ dy[i];
            if(nx>=0 && ny>=0 && nx < m && ny < n)
            {
                if(MAP[nx][ny] == Color && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx,ny));
                    Size++;
                }
            }
        }
    }
    return Size;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) 
{
    for(int i = 0 ; i <m;i++)
    {
        for(int j = 0 ; j < n; j++)
        {
            Visit[i][j] = false;
        }
    }
    int number_of_area = 0;
    int max_size_of_one_area = 0;  
    for(int i = 0; i < m; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(picture[i][j] != 0 && Visit[i][j] == false)
            {
                int Size = BFS(i, j, m, n, picture);
                if(Size > max_size_of_one_area) max_size_of_one_area = Size;
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}