[백준][1992] 쿼드 트리
[백준][1992] 쿼드 트리
이 포스트는 백준 사이트의 쿼드 트리 문제 풀이입니다.
문제
해결 과정
이 문제는 문제를 작은 문제로 나눠 해결하는 DP를 활용해 풀 수 있습니다.
사각형이 4개의 부분으로 나뉘었을 때, 방문하는 순서는 아래와 같습니다.
| 1 | 2 |
|---|---|
| 3 | 4 |
재귀 함수를 이용한 방문을 처리하면 1번부터 4번까지 한 번씩 탐색을 하면 됩니다.
괄호가 입력되는 순간은 현재 탐색되는 부분에서 한 깊이 더 내려갈 때, 괄호를 출력하면 됩니다.
코드에서 주의할 점은 N의 크기가 1이거나
이미 사각형이 압축 가능한 형태(모든 위치의 값이 동일)라면
재귀 함수를 호출할 필요가 없습니다.
코드 구현
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
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> board;
bool check_board(int row, int col, int size);
void DP(int row, int col, int size);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
board.assign(N + 1, vector<int>(N + 1, 0));
for(int row = 1; row <= N; ++row) {
string str;
cin >> str;
for(int col = 1; col <= N; ++col) {
board[row][col] = int(str[col - 1] - '0');
}
}
if(N == 1 || check_board(1, 1, N)) {
printf("%d", board[1][1]);
} else {
printf("(");
DP(1, 1, N / 2);
printf(")");
}
return 0;
}
bool check_board(int row, int col, int size) {
int curr_sign = board[row][col];
for(int r = row; r < row + size; ++r) {
for(int c = col; c < col + size; ++c) {
if(curr_sign != board[r][c]) return false;
}
}
return true;
}
void DP(int row, int col, int size) {
if(check_board(row, col, size)) {
printf("%d", board[row][col]);
}
else {
printf("(");
DP(row, col, size / 2);
printf(")");
}
if(check_board(row, col + size, size)) {
printf("%d", board[row][col + size]);
}
else {
printf("(");
DP(row, col + size, size / 2);
printf(")");
}
if(check_board(row + size, col, size)) {
printf("%d", board[row + size][col]);
}
else {
printf("(");
DP(row + size, col, size / 2);
printf(")");
}
if(check_board(row + size, col + size, size)) {
printf("%d", board[row + size][col + size]);
}
else {
printf("(");
DP(row + size, col + size, size / 2);
printf(")");
}
}
실행 결과
