프로그래밍/Python
[Python] 백준 1992 쿼드트리
모영이
2021. 3. 3. 18:32
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
분할 정복 : 시작점을 기준으로 +d만큼 탐색을 한다. 만약 압축 실패시 분할 압축.
전체 코드
import sys
input = sys.stdin.readline
def apchuk(si, sj, d, result):
color = graph[si][sj]
isTrue = True
for i in range(si, si + d):
for j in range(sj, sj + d):
if graph[i][j] != color:
isTrue = False
if not isTrue:
result.append('(')
d = d // 2
apchuk(si, sj, d, result)
apchuk(si, sj + d, d, result)
apchuk(si + d, sj, d, result)
apchuk(si + d, sj + d, d, result)
result.append(')')
else:
result.append(str(color))
return
N = int(input())
graph = []
result = []
for i in range(N):
graph.append(list(map(int, list(input().strip()))))
apchuk(0, 0, N, result)
for i in range(len(result)):
print(result[i], end = "")