문제
https://www.acmicpc.net/problem/1992
풀이
- 쿼드트리
- 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
- 만약 0과 1이 섞여 있으면?
- 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 영상으로 나누어 압축
- 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현
색종이 만들기 문제와 굉장히 유사하다.
즉, 분할 정복을 활용한 문제입니다.
문제만 봐서는 이해하기 힘들 수 있습니다.
예제를 통해서 이해를 해볼게요.
0과 1로 이루어진 2차원 배열이 있을 때, 모든 점이 0이나 1로 이루어져 있을 경우 0 또는 1로만 나타낼 수 있습니다.
하지만 예제는 모든 점이 하나로 통일되어 있지 않기 때문에 분할을 해줄 겁니다.
왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4분할을 해줄게요
이렇게 나누어서 다시 확인을 해보겠습니다.
2사분면을 보면 모두 0으로 이루어져 있는 것을 확인할 수 있습니다.
다음으로 1사분면을 확인하겠습니다.
1사분면을 보면 0과 1이 섞여있죠?
그렇기 때문에 분할을 한 번 더 진행해주겠습니다.
이제 모두 0과 1로 이루어지게 분할이 되었습니다.
같은 방식으로 3사분면도 각 사분면이 모두 0과 1만 남을 때까지 분할을 해줍니다.
4사분면은 모두 1로 이루어져 있기 때문에 분할을 진행하지 않아도 됩니다.
그래서 모두 분할을 진행하게 되면
이런 식으로 분할이 됩니다.
이를 2사분면부터 값을 출력하게 되면
- 0
- 0011
- 0(0111)01
- 1
이 출력하게 됩니다.
이를 괄호로 묶어주게 되면
(0(0011)(0(0111)01)1)가 나오게 됩니다.
같은 방식으로 예제 입력 값을 이용해 문제를 풀어보겠습니다.
모든 값이 통일되어 있지 않으므로 각 영역의 값이 통일 될 때까지 분할을 진행하겠습니다.
이제 각 영역이 통일되었습니다.
이를 출력하게 되면
예제 출력과 같은 값이 나왔죠?
이제 코드를 작성해봅시다.
def func(x, y, n): # 시작 좌표(x,y) 길이 n
tmp = arr[x][y] # 현재 위치
for i in range(x, x+n):
for j in range(y, y+n):
if arr[i][j] != tmp: # 현재 위치의 값과 검사하려는 좌표의 값이 다르다면
half = n // 2
# 좌상 → 우상 → 좌하 → 우하 순서로 재귀 호출
return "(" + func(x, y, half) + func(x, y+half, half) + func(x+half, y, half) + func(x+half, y+half, half) + ")"
return str(tmp) # 리턴 시 정수형 tmp 값이 괄호와 합쳐져야 하기 때문에
# 문자열로 선언해야 오류가 발생하지 않습니다.코드
import sys
input = sys.stdin.readline
def func(x, y, n):
tmp = arr[x][y]
for i in range(x, x+n):
for j in range(y, y+n):
if arr[i][j] != tmp:
half = n // 2
return "(" + func(x, y, half) + func(x, y+half, half) + func(x+half, y, half) + func(x+half, y+half, half) + ")"
return str(tmp)
if __name__ == "__main__":
n = int(input())
arr = [list(map(int, input().rstrip())) for _ in range(n)]
print(func(0, 0, n))