Level 2. 카카오프렌즈 컬러링북

Level 2. 카카오프렌즈 컬러링북

 

 

전형적인 완전 탐색 문제다.

• DFS가 깔끔해서 썼지만 BFS로 풀 수도 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int rDFS(unsigned i, unsigned j, int color, vector<vector<int>>& picture)
{
    if (picture.size() <= i || picture.front().size() <= j || picture[i][j] != color)
        return 0;

    picture[i][j] = 0;

    return rDFS(i - 1, j, color, picture) +
           rDFS(i + 1, j, color, picture) +
           rDFS(i, j - 1, color, picture) +
           rDFS(i, j + 1, color, picture) + 1;
}

vector<int> solution(int m, int n, vector<vector<int>> picture)
{
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    for (unsigned i = 0; i < m; ++i)
        for (unsigned j = 0; j < n; ++j)
            if (picture[i][j])
                max_size_of_one_area = max(max_size_of_one_area, rDFS(i, j, picture[i][j], picture)),
                ++number_of_area;

    return {number_of_area, max_size_of_one_area};
}