카카오 프렌즈 컬리링북 (프로그래머스)

영역을 구하기 위해서는 BFS(너비 우선 탐색)를 사용해야 한다. 

https://lipcoder.tistory.com/entry/%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-BFS?category=843242

너비 우선 탐색 (BFS)

특정 위치에서 시작하는 경우 현재 BFS를 이용해 양 방향으로 갈 수 없을 때까지 검사한다. 갈 수 없는 조건을 다음과 같다.

-> 해당 색과 다른 색인 경우 (혹은 색칠하지 않은 경우)
-> 컬러링북 크기를 넘어가는 경우 
-> 이미 방문한 위치인 경우

해당 작업을 거치면 특정 위치 색에 맞는 영역을 알 수 있다. 

 

이렇게 그림의 모든 위치를 검사한다. 이미 방문했거나 색칠되지 않은 경우에는 다음 위치로 넘어간다.

 

코드는 다음과 같다.

#include <vector>
#include <queue>
using namespace std;

// 너비 탐색을 위한 함수
int bfs(int x, int y, int color, int m, int n, const vector<vector<int>>& pic, vector<vector<bool>>& pass_info)
{
   // 해당 위치의 양 방향 위치값을 큐에 넣는다.
    queue<vector<int>> q;
    q.push(vector<int>{y + 1, x}); q.push(vector<int>{y - 1, x});
    q.push(vector<int>{y, x + 1}); q.push(vector<int>{y, x - 1});
    
    int count = 0;
    // 큐가 빌때까지
    while(!q.empty())
    {
        vector<int> info = q.front();
        q.pop();
        // 검사할 위치가 컬러링북 영역을 벗어난 경우
        if(info[0] >= m || info[0] < 0) continue;
        if(info[1] >= n || info[1] < 0) continue;
        // 검사할 위치가 이미 방문한 곳이거나 다른 색인 경우
        if(pass_info[info[0]][info[1]] == true || pic[info[0]][info[1]] != color) continue;
        
        // 해당 위치의 양 방향 위치값을 큐에 넣는다.
        q.push(vector<int>{info[0] + 1, info[1]}); q.push(vector<int>{info[0] - 1, info[1]});
        q.push(vector<int>{info[0], info[1] + 1}); q.push(vector<int>{info[0], info[1] - 1});
        
        // 해당 위치를 방문한것으로 갱신한다.
        pass_info[info[0]][info[1]] = true;
        // 영역 크기 값을 증가시킨다.
        ++count;
    }
    
    return count;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    // 방문 여부를 알 수 있도록 해주는 컨테이너
    vector<vector<bool>> passed(m, vector<bool>(n, false));

    // 모든 위치를 순회한다.
    for(int i = 0; i < picture.size(); ++i)
    {
        for(int j = 0; j < picture[i].size(); ++j)
        {
            // 색이 칠해져 있고 방문한 적이 없는 위치인 경우
            if(passed[i][j] == false && picture[i][j] != 0)
            {
                // 너비 우선 탐색을 이용해 영역의 크기를 구한다.
                int area_size = bfs(j, i, picture[i][j], m, n, picture, passed);
                if(max_size_of_one_area < area_size) max_size_of_one_area = area_size;
                ++number_of_area;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}