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

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

BFS를 사용하여 해결할 수 있는 문제입니다.

 

문제 접근법

• 전체 범위에 대해서 BFS를 통한 탐색을 시작하되, 그 범위를 한번도 탐색한 적이 없고, 0이 아닐 때 BFS 함수를 호출합니다.
• BFS가 호출 됬을 때 마다 새로운 영역이 있다는 의미가 되므로 영역 갯수를 증가시켜줍니다.
• BFS를 통해 영역의 넓이를 구하고 영역의 최대값을 갱신합니다.
• 모든 탐색이 끝나면 영역 갯수와 영역의 최대 넓이를 리턴합니다.

아래는 코드입니다.

#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int mM,nN;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool check[100][100];
 
bool InRange(int x, int y)
{
    return x >= 0 && x < mM && y >= 0 & y < nN;
}
 
int bfs(int x, int y, vector<vector<int>> picture)
{
    int size = 1;
    int color = picture[x][y];
    
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
    
    while(!q.empty())
    {
        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(InRange(nx, ny) && !check[nx][ny] && picture[nx][ny] == color)
            {
                check[nx][ny] = true;
                q.push(make_pair(nx, ny));
                size++;
            }
        }
    }
    
    return size;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    mM = m;
    nN = n;
    
    memset(check, false, sizeof(check));
    
    vector<int> answer;
    
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!check[i][j] && picture[i][j] != 0)
            {
                max_size_of_one_area = max(max_size_of_one_area, bfs(i, j, picture));
                number_of_area++;
            }
        }
    }
    
    answer.push_back(number_of_area);
    answer.push_back(max_size_of_one_area);
    
    return answer;
}