1️⃣서론
백준 문제 1992번 쿼드트리 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣문제 설명
이 문제는 쿼드트리라는 방법으로 데이터를 압축하여 표현한 결과를 출력하는 문제입니다.
3️⃣풀이
이 문제는 분할정복의 대표적인 문제입니다.
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
import sys
def divideConquer(x, y, n):
global arr
check = arr[x][y]
for i in range(x, x + n):
for j in range(y, y + n):
if check != arr[i][j]:
print('(', end="")
divideConquer(x, y, n // 2)
divideConquer(x, y + n // 2, n // 2)
divideConquer(x + n // 2, y, n // 2)
divideConquer(x + n // 2, y + n // 2, n // 2)
print(')', end="")
return
print(check, end="")
N = int(input())
arr = []
for _ in range(N):
arr.append(list(map(int, sys.stdin.readline().strip())))
divideConquer(0, 0, N)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
