프로그래머스 (Level 2) : 카카오프렌즈 컬러링북/ C++, BFS/ 2017 카카오코드 예선

문제

프로그래머스

 

카카오 문제들은 항상 프렌즈 캐릭터가 예시로 나온다.

프렌즈들은 넘나 귀엽지만.. 문제로 만나면 왠지 화가난다.. 귀여운척하지마 악랄한것아

 

문제 예시 그림 (출처 : 프로그래머스)

 

그림에서 상하좌우가 같은 색으로 연결된 경우를 '한 영역'으로 친다.

위 그림의 경우는 총 12영역이다. (눈6, 입3, 볼2, 얼굴1)

 

영역의 개수와 가장 넓은 영역의 넓이를 return하는 문제이다.

 

예제 1
입력값 〉	6, 4, [[1, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1]]
기댓값 〉	[2, 6]

예제 2
입력값 〉	6, 4, [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]
기댓값 〉	[4, 5]

 

 

풀이

#include <vector>
#include <deque>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

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

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<int> answer(2);
    vector<vector<int>> v(m,vector<int>(n,0)); //visit
    deque<pair<int,int>> dq;
    int cnt=0, max_cnt=0, area_cnt=0;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(v[i][j]==0 && picture[i][j]!=0){
                int val=picture[i][j];      //시작영역 값
                dq.push_back(make_pair(i,j)); //영역 시작 위치
                v[i][j]=1;                  //visit
                cnt=0;                      //영역 개수 초기화
                area_cnt++;                 //영역 추가
                while(!dq.empty()){
                    int cx=dq[0].first;
                    int cy=dq[0].second;
                    dq.pop_front();
                    cnt++;
                    
                    for(int k=0;k<4;k++){
                        int nx = cx+dx[k];
                        int ny = cy+dy[k];
                        if(nx>=0 && nx<m && ny>=0 && ny<n &&
                           v[nx][ny]==0 && picture[nx][ny]==val){
                            dq.push_back(make_pair(nx,ny));
                            v[nx][ny]=1; //visit
                        }
                    }
                }
                if(max_cnt<cnt)max_cnt=cnt;
            }
        }
    }
    
    // for(int i=0;i<v.size();i++){
    //     for(int j=0;j<v[i].size();j++){
    //         cout<<v[i][j]<<" ";    
    //     }
    //     cout<<endl;
    // }
    
    answer={area_cnt, max_cnt};
    return answer;
}

 

BFS로 풀었고 처음 picture 배열을 탐색하다 방문하지 않고 picture 값이 0이 아닌 경우

picture 값을 저장하고 해당 위치를 큐에 넣어 다음 위치값이 저장한 값과 같고 방문하지 않은 위치를 큐에 넣어 반복했다.

 

 

 

*2차원 벡터 사용법 참고 : vector<vector<int>> v(m,vector<int>(n,default_value))

C++에서 2차원 벡터 초기화