[백준 1992] - 쿼드트리(Silver I)

📒문제

🎈풀이

import sys

def compress(row, col, size):
  global result

  if size == 1:
    result += str(arr[row][col])
    return

  isAble = False

  for i in range(row, row+size):
    for j in range(col, col+size):
      if arr[i][j] != arr[row][col]:
        isAble = True
        break
    if isAble: break

  if isAble:
    result += "("
    compress(row, col, size//2)
    compress(row, col+size//2, size//2)
    compress(row+size//2, col, size//2)
    compress(row+size//2, col+size//2, size//2)
    result += ")"
  else:
    result += str(arr[row][col])


arr = []
result = ""
N = int(sys.stdin.readline().rstrip())

for _ in range(N):
  arr.append(list(map(int, sys.stdin.readline().rstrip())))

compress(0, 0, N)

print(result)

처음에 봤을 때 예제가 이해가 안 되서 고민했었던 문젠데, 예제를 이해하고 나선 그동안 풀었던 종이 자르는 재귀 문제와 거의 비슷해 쉽게 풀 수 있었던 문제이다. 역시 한 번이라도 스스로 풀어본 문제 유형은 기억에 잘 남는 것 같다.