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

아 진짜 이 문제 너무 스트레스 받았던 문제이다. 

 

아무리 봐도 틀린게 하나도 없는데 기본 예제만 통과하고 최종은 계속 통과가 되지 않았다. 

비쥬얼스튜디오까지 켜가면서 확인을 해가며 배열의 변화 과정 까지 차근차근 살펴봐도 틀린 부분이 없었다. 

 

그래서 프로그래머스 질문하기 페이지에 들어가서 확인해봤는데 문제 오류;; 스트레스가 하늘을 치솟았다. 

이 문제에 거의 4시간을 쓴거 같다. 

 

해당 문제는 애초에 전역변수를 생성 하지 말라고 한다.

생성한 전역변수를 solution 함수에 다 넣고 파라미터 값을 변수의 주소를 담아와서 구현을 하였다. 

그렇게 하니 문제가 통과되었다. 

---

해당 문제는 bfs를 활용하면 쉽게 풀 수 있다. 

지금껏 내가 다뤄왔던 bfs 문제는 항상 비슷한 맥락이였다. 구현을 하기에 살짝 변형한 것 뿐이지,

Queue<pair<int,int>> q  변수에 x와 y 값을 넣어서 차례대로 뽑아서 주변을 살펴 보는 것이다. 

이 문제도 비슷하다. 

 

 

이 예제를 활용 해보자.

먼저 picture 안에 입력값이 저장되어 있을 것이다. 그리고 0으로 초기화된 visited 배열을 생성 해주자. 

bfs를 돌리기 위한 조건은 먼저 아직 방문하지 않은 구간과 그리고 picture 값이 0이 아닐 때 bfs를 돌리면 된다. 

bfs를 돌리기 위해 해당 함수로 이동할 때 카운트를 하나 증가 시켜주는데 그 값이 number_of_area 이며 

bfs함수 내에서 queue를 pop 해주고 push 해주는 과정이 그 영역에서의 count값이다. 

즉, 첫번째 bfs 돌릴 때 0,0 좌표 값에서 시작하게 되는데 picture의 (0,0) 값은 1이기 때문에 상,하,좌,우에 해당 값이 있으면 queue 넣으면서 visited를 갱신해 나간다. 주변을 다 살피게 되면 visited 를 갱신해준 개수가 하나의 영역의 범위라고 생각하면 되고 다른영역 또한 이와 같이 수행하고 그 값이 최대인 값을 저장 시켜주면 된다. 

#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
queue <pair<int,int>> q;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int bfs(int number, int m, int n, int check, vector<vector<int>> &map, int max_num, vector<vector<int>> &visited){    
    int x, y; 
    int dx[4]={0,0,1,-1}; 
    int dy[4]={1,-1,0,0}; 
    while(!q.empty()){
        tie(y,x)=q.front(); 
        q.pop(); 
        for(int i=0; i<4; i++){
            int nx = x+dx[i]; 
            int ny = y+dy[i]; 
            if(nx<0||nx>=n||ny<0||ny>=m||visited[ny][nx])continue; 
            if(map[ny][nx]!=check)continue;
            number++; 
            visited[ny][nx]=1;             
            q.push({ny,nx}); 
        } 
    }
    return number;     
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;    
    int max_num=0; 
    vector <vector <int>> visited; 
    for (int i = 0; i < m; i++) {
        vector <int> v(n);
        for (int j = 0; j < n; j++) {    
            v[j] = 0; 
        }
        visited.push_back(v); 
    }    
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(picture[i][j]!=0&&visited[i][j]==0){
                q.push({i,j});
                visited[i][j]=1;       
                number_of_area++;                
                max_num = max(max_num, bfs(1, m,n, picture[i][j], picture, max_num, visited) );
            }
        }
    }       
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_num;
    return answer;
}