처음으로 참가한 알고리즘 대회인데, 이 대회 덕분에 알고리즘 공부를 시작하게 되었죠. 본선 진출 1문제 차이로 탈락했었습니다.

이 문제는 1번 문제인데요, 행렬로 주어진 그림에서 영역(상하좌우에서 같은 색으로 된 부분은 같은 영역)의 갯수와 최대 영역의 크기를 구하는 문제입니다. 재귀 문제입니다. flood_fill 알고리즘을 이용해서 푸시면 됩니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <vector>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int M;
int N;
vector<vector<int>> Pic;

int flood_fill(int m, int n,int col)
{
 int sum = 0;
 if (col == 0) { // 색상이 다르면 종료
  return 0;
 }
 if (n > 0 && col == Pic[m][n - 1] ) // left, 색상이 같으면 재귀적으로 진행
 {
  Pic[m][n] = 0; // 해당 영역은 색상을 없애고
  sum += flood_fill(m, n - 1, col); // 왼쪽으로 수행
 }
 if (n <  N - 1 && col == Pic[m][n+1] ) // right
 {
  Pic[m][n] = 0;
  sum += flood_fill(m, n + 1, col);
 }
 if (0 < m && col == Pic[m - 1][n]) //above
 {
  Pic[m][n] = 0;
  sum += flood_fill(m - 1, n, col);
 }
 if (m < M - 1 && col == Pic[m+1][n]) // below
 {
  Pic[m][n] = 0;
  sum += flood_fill(m + 1, n, col);
 }
 
 Pic[m][n] = 0;
 return 1+sum;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    
 int cnt_area, max_area, temp;
    Pic.clear();
    Pic = picture;
 M = m;
 N = n;
 cnt_area = 0;
 max_area = 0;
 temp = 0;
 vector<int> answer;

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

  for (int j = 0; j<n; j++)
  {
   max_area = flood_fill(i, j, Pic[i][j]); // 최대 크기값을 반환
   if (max_area != 0) // 색상 영역이 존재하는 경우
   {
    cnt_area++; // 영역 카운트+
    if (temp < max_area) // max값인지 확인
     temp = max_area;
    max_area=0;
   }
   
  }
 }

 answer.push_back(cnt_area);
 answer.push_back(temp);
    
    return answer;
}