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

출처 프로그래머스

https://programmers.co.kr/

프로그래머스

 

2017 카카오 코드 예선 문제이다.

4방향 순회를 재귀함수로 구현하여 문제를 해결하였다.

#include <vector>
#define NON_COLOR 0
 
using namespace std;
int traversal(vector<vector<bool>>& check,vector<vector<int>>& picture, int color,int count,int row, int column) {
 
    if (color != picture[row][column] || check[row][column] == true)
        return 0;
 
    check[row][column] = true;
    if(column != picture[0].size()-1)
        count += traversal(check, picture, color, 0, row, column +1);
    if(column != 0)
        count += traversal(check, picture, color, 0, row, column -1);
    if(row != picture.size()-1)
        count += traversal(check, picture, color, 0, row +1, column);
    if(row != 0)
        count += traversal(check, picture, color, 0, row -1, column);
    return count+1;
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    int size = 0;
    vector<vector<bool>> already_check(m, vector<bool>(n,false));
 
    for (int row = 0; row < m; row++) {
        for (int column = 0; column < n; column++) {
            if (already_check[row][column] || picture[row][column] == NON_COLOR)
                continue;
            size = traversal(already_check, picture, picture[row][column], 0, row, column);
            if (max_size_of_one_area < size) 
                max_size_of_one_area = size;
            if (size != 0)
                number_of_area++;
            size = 0;
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

vector<vector<bool>> already_check(m, vector<bool>(n,false));

already check 라는 bool vector를 만들어 이미 방문한 영역을 표시하였고

 

int traversal(vector<vector<bool>>& check,vector<vector<int>>& picture, int color,int count,int row, int column)에서

재귀함수로 traversal 함수를 구성하여 상하좌우 모두 탐색하게 하였다.

방문한 영역이 기존영역의 색깔과 다르거나 방문한 영역이 기존에 이미 방문한 영역일 때 재귀를 중단하였다.

 

  for (int row = 0; row < m; row++) {

        for (int column = 0; column < n; column++) {

            if (already_check[row][column] || picture[row][column] == NON_COLOR)

                continue;

            size = traversal(already_check, picture, picture[row][column], 0, row, column);

            if (max_size_of_one_area < size) 

                max_size_of_one_area = size;

            if (size != 0)

                number_of_area++;

            size = 0;

        }

    }

solution의 이중포문에서

이미 방문한 영역이거나 NON_COLOR (picture값이 0)인 경우엔 순회를 하지 않았으며

 

순회 후 사이즈와 max_size_of_one_area 를 비교하여 max_size를 갱신하여 가장 큰 영역의 넓이를 계산하였고,

 

size가 0이 아닌 경우엔 새로운 영역을 찾은 것이라 판단하여 number_of_area에 1을 더해주었다.