[ BOJ / 파이썬 ] 1992 쿼드트리

/ 제출 1 /

import sys
input = sys.stdin.readline
n = int(input())
board = [list(input()) for _ in range(n)]

def quadtree(startX,startY, endX, endY):
  print('(')
  compress = board[0][0]
  canCompress = True
  input()
  for i in range(startX, endX):
    for j in range(startY, endY):
      print(board[i][j], end="")
      if compress != board[i][j]:
        canCompress = False
    print("")
  if endX - startX <= 1:
    return compress
  else:
    print(quadtree(0, 0, endX//2, endY//2))
    print(quadtree(0, startY//2, endX//2, endY))
    print(quadtree(startX//2, 0, endX, endY//2))
    print(quadtree(startX//2, startY//2, endX, endY))
  print(')')
quadtree(0, 0, n, n)

: 무한루프 돌면서 터집니다.

 

1. 함수 정의

def quadtree(startX,startY, endX, endY):

 

2. base condition

if endX - startX <= 1:
    return compress

: 사실 

n = 2일 때,

    압축 가능?(4개가 다 같음?) 맞으면, 그 숫자 리턴

                                                 아니면, 그 배열 리턴
으로 구현하고 싶었는데, 잘 안 됐다.

 

3. 재귀 식

  print(quadtree(0, 0, endX//2, endY//2))
  print(quadtree(0, startY//2, endX//2, endY))
  print(quadtree(startX//2, 0, endX, endY//2))
  print(quadtree(startX//2, startY//2, endX, endY))

 

:4등분으로 쪼개 각자의 재귀로 말려들어가게 했다.

 

:

뭐.. 가 문제였을까. 왜 혼자 힘으로 풀 수 없는걸까.. 하아.. 다른 사람들 풀이 보고 정리하기로.

 

---

import sys
input = sys.stdin.readline
n = int(input())
board = [list(map(int, input().strip())) for _ in range(n)]

def quadtree(x, y, n):
  if n == 1:
    print(board[x][y], end="")
    return 
    
  canCompress = True
  for i in range(x, x+ n):
    if not canCompress:
      break
    for j in range(y, y + n):
      if board[i][j] != board[x][y]:
        canCompress = False
        break
        
  if canCompress:
    print(board[x][y], end="")
  else:
    print('(', end="")
    quadtree(x, y, n//2)
    quadtree(x, y + n//2, n//2)
    quadtree(x + n//2, y, n//2)
    quadtree(x + n//2, y + n//2, n//2)
    print(')', end="")
quadtree(0, 0, n)

 

와.. 수정하면서 괜한데서 잘못해서 시간 꽤 잡아먹었다..

그래도 이제 디버깅이 된다 .. 그것에 만족해야하나..

 

하여간 이제 분할 정복 어떤 식인지 감은 잡히는 것 같다. 코드 구현이 안 돼서 그렇지.

오늘 밤새 열심히 재귀 문제 달려보자.