[프로그래머스/Level 2] 카카오프렌즈 컬러링북 (C++)

programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

전형적인 BFS 문제로 어렵지 않은 문제다. 다만 영역을 구할 때 값이 매번 바뀌므로, 이를 tmp에 저장하고 큐의 탐색이 진행되어야 한다.

 

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

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

int BFS(int r, int c, vector<vector<int>> &picture) {
    int sum = 1;
    int pivot = picture[r][c]; // 영역마다 값이 다르므로 큐의 탐색에서 비교의 기준이 될 변수
    queue<pair<int, int > > q;
    q.push({ r, c });
    picture[r][c] = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < row && ny >= 0 && ny < col) {
                if(picture[nx][ny] == pivot) {
                    q.push({ nx, ny });
                    picture[nx][ny] = 0;
                    sum++;
                }
            }
        }
    }
    
    return sum;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0, max_size_of_one_area = 0; // 전역변수로 선언하면 틀렸다고 나옴
    row = m;
    col = n;
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            if(picture[i][j] != 0) {
                max_size_of_one_area = max(max_size_of_one_area, BFS(i, j, picture));
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

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

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

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    queue<pair<int, int> > q;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            int sum = 0;
            if(picture[i][j] != 0) {
                q.push({i, j});
                int tmp = picture[i][j]; // 영역마다 값이 다르므로 큐의 탐색에서 비교를 위해 저장
                picture[i][j] = 0;
                sum++;
                while(!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for(int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                            if(picture[nx][ny] == tmp) {
                                q.push({nx, ny});
                                picture[nx][ny] = 0;
                                sum++;
                            }
                        }
                    }
                }
                max_size_of_one_area = max(max_size_of_one_area, sum);
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}