프로그래머스, 카카오프렌즈 컬러링북 : C++ [CPP]

어렵지 않았다.

다만 전역변수 초기화를 안해서 20분동안 헤맸다.

https://programmers.co.kr/learn/courses/30/lessons/1829#

 

---

 

#맞는 풀이

#include <vector>
#include <queue>

#define X first
#define Y second

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

using namespace std;

int visited[100][100];
queue <pair<int,int>> q;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            visited[i][j] = 0;
        }
    }
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(visited[i][j] == 0 && picture[i][j] != 0){
                number_of_area++;
                int flag = picture[i][j];
                int size = 0;
                visited[i][j] = 1;
                q.push({i,j});
                size++;
                while(!q.empty()){
                    auto cur = q.front();
                    q.pop();
                    for(int dir = 0; dir<4; dir++){
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        
                        if(nx<0 || nx>=m || ny<0 || ny>=n)continue; //범위
                        if(visited[nx][ny] != 0 || picture[nx][ny] != flag)continue;// 이미 방문했거나 같은 flag가 아닐 경우
                        visited[nx][ny] = 1;
                        q.push({nx,ny});
                        size++;
                    }
                }
                if(size >= max_size_of_one_area) max_size_of_one_area = size;
            }
        }
    }
    
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

 

BFS로 탐색했다.

size는 area를 조사할 때마다 max로 갱신하였고

area는 처음 시작하는 노드의 개수와 같았다.

 

초기화를 안해서 헤맸다.

 

프로그래머스에서의 방식은

제출된 함수를 계속 돌리는 것인가 보다

때문에 test case가 맞더라도 전역변수를 초기화 하지 않으면 진행이 되질 않는다.