문제
풀이
분할 정복으로 풀 수 있는 문제이다.
우선 처음에 NxN 크기의 배열을 탐색하며 가장 왼쪽 위의 수와 다른 수가 나오면 (N/2)x(N/2)크기로 4등분하여 재귀 함수를 호출하는 형식으로 구현했다.
4개의 재귀함수를 호출하기 전과 후에 각각 ‘(‘ 와 ‘)’을 출력하여 출력형식을 맞춘다. 코드를 보며 확인해보자.
소스 코드
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
#include <iostream>
#include <string>
using namespace std;
string video[64];
// 재귀함수
void printCompResult(int size, int y, int x)
{
char curr = video[y][x];
for (int i = y; i < y + size; i++)
for (int j = x; j < x + size; j++)
if (video[i][j] != curr)
{
cout << '(';
printCompResult(size / 2, y, x);
printCompResult(size / 2, y, x + size / 2);
printCompResult(size / 2, y + size / 2, x);
printCompResult(size / 2, y + size / 2, x + size / 2);
cout << ')';
return;
}
cout << curr;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> video[i];
printCompResult(N, 0, 0);
return 0;
}
