[#9][알고리즘] 카카오 코드 페스티벌 예선 - 카카오 프렌즈 컬러링북 풀이(Flood fill 알고리즘)
카카오 코드 페스티벌 예선 > 카카오 프렌즈 컬러링북 풀이(Flood fill 알고리즘)
Flood fill : 경계 내의 어떤 영역을 특정한 색으로 칠하는 문제(재귀 이용)C++ 풀이
#include <vector>
using namespace std;
vector<vector<int>> pic;
int ff(int m, int n, int color) {
int area = 1; // color가 0이 아니기 때문
if (n > 0 && color == pic[m][n-1]) {
// left
pic[m][n] = 0; // color가 같은지 확인 후 색 지워버리기
area += ff(m, n - 1, color);
}
if (n < pic[0].size() - 1 && color == pic[m][n + 1]) {
// right
pic[m][n] = 0;
area += ff(m, n + 1, color);
}
if (m > 0 && color == pic[m - 1][n]) {
// above
pic[m][n] = 0;
area += ff(m - 1, n, color);
}
if (m < pic.size() - 1 && color == pic[m + 1][n]) {
// below
pic[m][n] = 0;
area += ff(m + 1, n, color);
}
pic[m][n] = 0; // 주변에 같은 색이 없는 경우
return area;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
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;
pic = picture;
vector<int> answer(2);
for (int i = 0; i < m; i++) {
for (int j = 0; j <n; j++) {
if (pic[i][j] != 0) {
size = ff(i, j, pic[i][j]);
// 영역이 존재한다.
number_of_area++;
// 반환된 최대 영역 크기 중 max를 찾는다.
if (max_size_of_one_area < size) max_size_of_one_area = size;
}
}
}
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}
| cs |
댓글
댓글 쓰기