[C++] 카카오프렌즈 컬러링북( queue를 사용한 bfs 풀이)

코딩 테스트 보기 전에 C++ 손풀기로 매번 푸는 dfs문제. 매번 풀 때마다 풀이가 달라지는걸 보는것도 재미있다. 

풀고 비교해 보니 이전에 풀었던 코드는 visited vector를 손수 for문으로 초기화했었다. vector 초기화 방법을 몰랐나보다.

이번에는 재

그래도 조금씩 발전하면서 깔끔해지는 중.

 

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

using namespace std;

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

queue<pair<int,int>> q;
int bfs(vector<vector<int>> &picture,vector<vector<bool>> & visited, int x,int y,int m,int n){
    int count = 1;
    int curColor = picture[x][y];
    int curX = x;
    int curY = y;
    
    while(!q.empty()){
        for(int i = 0;i<sizeof(dx)/sizeof(dx[0]);i++){
            if(curX+dx[i]>=m || curX+dx[i]<0 || curY+dy[i]>=n || curY+dy[i]<0)
                continue;
            if(picture[curX+dx[i]][curY+dy[i]] ==curColor && !visited[curX+dx[i]][curY+dy[i]])  {
                q.push({curX+dx[i],curY+dy[i]});
                visited[curX+dx[i]][curY+dy[i]] = true;
                ++count;
            }
        }
        q.pop();
        curX = q.front().first;
        curY= q.front().second;
    }
    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>> visited (m,vector<bool>(n,false));

    for(int i = 0;i<m;i++){
        for(int j = 0;j<n;j++){
            if(picture[i][j]!=0 && !visited[i][j]){
                q.push({i,j});
                visited[i][j] = true;
                
                int newCount = bfs(picture,visited, i,j,m,n);
                if(newCount > max_size_of_one_area)
                    max_size_of_one_area = newCount;
                ++number_of_area;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}