[백준 1992번] 쿼드트리 -python

문제 링크

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

풀이

- 분할 정복 문제 

- 범위의 제일 왼쪽 위의 값을 start 에 저장해놓고 범위 안에 start와 다른 값이 있을 경우 4등분하여 재귀적으로 호출한다.

   이 때 괄호를 쳐준다. 

- 만약 서로 다른 값이 없을 경우 start가 0 이면 result에 0 대입, 1이면 result에 1 대입 

result = []

def sol(x,y,n):
  start = graph[x][y]
  
  global result 

  for i in range(x, x+n):
    for j in range(y, y+n):
      if start != graph[i][j]:
        result.append('(')
        sol(x, y, n//2)
        sol(x, y+n//2,n//2)
        sol(x+n//2, y, n//2)
        sol(x+n//2, y+n//2, n//2)
        result.append(')')
        return

  if start == 0:
    result.append('0')
  else:
    result.append('1')
    
n = int(input())

graph = []

for _ in range(n):
  graph.append(list(map(int,input())))

sol(0,0,n)
print("".join(result))