카카오 프렌즈 컬러링북
2019, Jun 02
- https://programmers.co.kr/learn/courses/30/lessons/1829
- connected componets를 찾는 문제입니다.
- board를 상하좌우 탐색하면서 같은 색으로 연결된 격자의 갯수와 최대 크기를 찾습니다.
- 아래 코드는 dfs를 이용하여 완전 탐색을 한 코드입니다.
- 이유는 모르겠으나 전역변수를 바로 선언하면 에러가 납니다. 왜그런지…
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> board;
vector<vector<int>> visited;
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };
int M, N;
int go(int y, int x, int color) {
if (y < 0 || y >= M || x < 0 || x >= N) {
return 0;
}
if (visited[y][x] == 1) {
return 0;
}
if (board[y][x] == 0 || board[y][x] != color) {
return 0;
}
visited[y][x] = 1;
int ret = 1;
for (int i = 0; i < 4; ++i) {
ret += go(y + dy[i], x + dx[i], color);
}
return ret;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
int number_of_area = 0;
int max_size_of_one_area = 0;
M = m;
N = n;
//board 초기화
board = picture;
//visited 초기화
vector<vector<int>>visited2(m, vector<int>(n, 0));
visited = visited2;
vector<int> areaSize;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int area = go(i, j, board[i][j]);
if (area != 0) {
areaSize.push_back(area);
}
}
}
if (areaSize.empty()) {
number_of_area = 0;
max_size_of_one_area = 0;
}
else {
auto iter = max_element(areaSize.begin(), areaSize.end());
number_of_area = areaSize.size();
max_size_of_one_area = *iter;
}
vector<int> answer(2);
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}