백준 1992 쿼드트리 (파이썬)
접근방식
- 백준 2630 색종이 만들기 문제와 똑같은 방식으로 분할정복 방법을 사용하여 푸는 방법이다. 어떤 규칙으로 분할을 하고 합칠 것인지가 관건이다. 2630 색종이 만들기 문제는 아래 링크에서 확인할 수 있다.
https://ataraxiady.github.io/dev/2021/04/10/dev-boj-1_2630/
- 이 문제의 분할 규칙은 마찬가지로
기준점(내 코드에서는 나뉘어진 배열의 0,0)과 다른 색이 나온다면 4등분 분할을 한다.이다. - 출력부분만 살짝 수정해주면 된다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
quadTree = []
for _ in range(n):
quadTree.append(list(map(int,sys.stdin.readline().strip())))
def check(n, i, j):
s = quadTree[i][j]
for ii in range(i, i + n):
for jj in range(j, j + n):
if quadTree[ii][jj] != s:
print('(',end='')
check(n // 2, i, j)
check(n // 2, i, j + (n // 2))
check(n // 2, i + (n // 2), j)
check(n // 2, i + (n // 2), j + (n // 2))
print(')',end='')
return
if s == 0:
print('0', end='')
return
else:
print('1', end='')
return
check(n, 0, 0)
