[C++] 카카오 프렌즈 컬러링북

Kakao2017 LEVEL 3 문제풀이

[출처] 프로그래머스

 

 

 

빈 공간이 아닌 부분을 찾아서 BFS를 돌리고 변수에 각각 영역의 수와 가장 큰 영역의 칸 수를 저장하면 된다.

 

전체 소스코드

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

using namespace std;

int dx[4] = {-1,1,0,0}; // 상 하 좌 우
int dy[4] = {0,0,-1,1};
int cnt, max_ar, tmp_ar, ar, cnt_ar;

void bfs(int n, int m, vector< vector<int> > picture){
    max_ar = tmp_ar = ar = cnt_ar = 0;

    queue < pair <int, int> > q;
    vector<vector<bool>> visit(m,vector<bool>(n,false));

    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(picture[i][j] != 0 && visit[i][j] == 0){
                cnt = 1;
                ar = picture[i][j];
                q.push(make_pair(i,j));
                visit[i][j] = true;
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for(int k = 0; k<4; k++){
                        int rx = x + dx[k];
                        int ry = y + dy[k];
                        if(rx >= 0 && ry >= 0 && rx < m && ry < n){
                            if(ar == picture[rx][ry] && visit[rx][ry] == false){
                                visit[rx][ry] = true;
                                q.push(make_pair(rx,ry));
                                cnt++;
                            }
                        }
                    }
                }
                cnt_ar++;
            }
            if(max_ar < cnt){
                max_ar = cnt;
                tmp_ar = ar;
            }
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {

    bfs(n,m,picture);

    vector<int> answer(2);
    answer[0] = cnt_ar;
    answer[1] = max_ar;
    return answer;
}