카카오프렌즈 컬러링북

코드

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

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 , -1, 0};
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<int>> vis(m);
    queue<pair<int,int>> q;
    // m=세로, n=가로
    /* vis 초기화 */
    for(int i=0;i<picture.size();i++) vis[i].resize(n);
    /* BFS 시작 */
    for(int i=0;i<picture.size();i++)
    {
        for(int j=0;j<picture[i].size();j++)
        {
            if(vis[i][j] || !picture[i][j]) continue;
            q.push({i,j});
            number_of_area++;
            int cnt=0;
            while(!q.empty())
            {
                auto cur = q.front(); q.pop();
                for(int d=0;d<4;d++)
                {
                    int nx = cur.second + dx[d];
                    int ny = cur.first + dy[d];
                    if(nx <0 || ny <0 || nx>=n || ny>=m) continue;
                    if(vis[ny][nx] || picture[ny][nx] != picture[cur.first][cur.second]) continue;
                    q.push({ny,nx});
                    vis[ny][nx] = 1;
                    cnt++;
                }
            }
            max_size_of_one_area = max(max_size_of_one_area, cnt);
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

• 정석적인 BFS 풀이