[백준 1992번] 쿼드트리 (Python/파이썬)

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

1992번: 쿼드트리

문제를 읽었을 때는 ~압축한다 라고 나와있어서 좌표압축 문제로 착각할 수 있지만, 좀만 더 읽어보면 분할정복이라는 것이 보인다.

특정 공간이 0또는 1로만 이루어지면 그 공간 전체를 0 또는 1로 압축한다고 하고, 전체를 압축한 결과를 내라는 문제이다.

종이의 개수나 색종이 만들기 문제와 비슷하지만 괄호를 어느 부분에 넣어야되냐가 생각하기가 조금더 어렵기 때문에 실버1의 난이도로 배정된것 같다. 

괄호의 위치를 생각하기 어렵다기 보단 재귀를 어느정도 이해해야지 괄호가 어느 위치로 들어갈지 정확히 맞출 수 있다.

규칙을 잘 보면 한번 4방면으로 분할 될때마다  '(' 가 들어가줘야하고, 특정 4방면의 탐색이 끝나면 ')' 를 넣어주어야한다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
N = int(input())
board = []
for i in range(N):
  string = list(input().rstrip())
  board.append(string)

Quad_tree = []
def divide(a,b,N):
  tmp = board[a][b]
  for i in range(a,a+N):
    for j in range(b,b+N):
      if board[i][j] != tmp:
        Quad_tree.append('(')
        divide(a,b,N//2)
        divide(a,b+N//2,N//2)
        divide(a+N//2,b,N//2)
        divide(a+N//2,b+N//2, N//2)
        Quad_tree.append(')')
        return
  Quad_tree.append(tmp)

divide(0,0,N)
print(*Quad_tree,sep = "")

 

 

 

 

 

 

 

 

 

 

글이나 코드에 대한 조언 환영합니다!