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

 

간단한 BFS 문제였다.

근데 문제에서 주의해야 할 점이 있다.

전역 변수로 선언할 경우 반드시 solution 내에서 초기화를 시켜줘야 한다.

이것만 주의한다면 나머진 쉽게 풀리는 문제다.

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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>> vis(101, vector<bool>(101, false));
    queue<pair<int, int>> Q;
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int tmp = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int area = 1;
            if (!vis[i][j] && picture[i][j] != 0) {
                number_of_area++;
                Q.push({ i,j });
                vis[i][j] = true;
                tmp = picture[i][j];
            }
            while (!Q.empty()) {
                auto cur = Q.front(); Q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (vis[nx][ny] || picture[nx][ny] != tmp) continue;
                    Q.push({ nx,ny });
                    vis[nx][ny] = true;
                    area++;
                }
            }
            max_size_of_one_area = max(max_size_of_one_area, area);
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

문제를 풀다 보면 BFS나 DFS 같은 경우는 특히 자신만의 정형화된 틀을 사용하는데 이 문제에선 그냥 전역 변수에 박아 넣고 푸는 게 정신건강에 이로운 것 같다.