[ BOJ / 파이썬 ] 쿼드트리

재귀 

 

재귀 문제에서 지금 반복해 연습 중인 도형 자르기 문제.

6개월 전 풀었던 풀이를 바탕으로 시간복잡도 줄이기 위해 코드를 정리해나가봤다.

 

우선, 

6개월 전 풀이.

# 하.. 처음에 quadtree짤 때, return 받아서 print하게 한 걸, 
# 수정하면서 같이 안 고쳐줘서 엄한 데서 오류 찾고 있었다. 시간 많이 잡아먹었다:-(
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)

n//2 를 매번 quadtree를 호출할 때마다 부르는데, 이게 자잘하게 시간이 걸리겠다 싶어 변수에 저장하기로 했다.

 

수정 뒤, 

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:
  ########################수정한 부분 #################
    halfN = n//2
    print('(', end="")
    quadtree(x, y, halfN)
    quadtree(x, y + halfN, halfN)
    quadtree(x + halfN, y, halfN)
    quadtree(x + halfN, y + halfN, halfN)
    print(')', end="")
  #######################  ############################
quadtree(0, 0, n)

77ms -> 44ms 로 절반으로 감소했다.

 

quadtree를 여러번 부르는 게 거슬렸다. for문으로 한 번에 돌려보기로 했다.

물론 한 번 나눌 때마다 1/4이라 지금은 큰 차이 없어도 이게 1/9 혹은 1/16뭐 이러면 그걸 일일히 작성해야할 것 같기에.

 

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:
    halfN = n//2
    print('(', end="")
  ########################수정한 부분 #################
    for i in range(2):
      for j in range(2):
        quadtree(x + i*halfN, y + j*halfN, halfN)
  #######################  ############################
    print(')', end="")
quadtree(0, 0, n)

 

시간소요는 이전 수정 버전과 같았다. 44ms 그러나 코드 길이가 줄었다. 865B -> 639B

 

그 다음 해당 비디오이미지가 통일되어서 압축 가능한 지 부분은 묘하게 구분되는 기능이므로 따로 빼는 게 낫겠다 싶었다.

for문의 구성 자체도 묘하게 마음에 안 들어서! early return이 가능하면 i 인덱스로 도는 for문에서 한 번씩 더 체크하는 과정을 안 거칠 수 있을 것 같았다.

 

수정 후

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

  ########################수정한 부분 #################
def canCompress(x, y, n):
  for i in range(x, x+ n):
    for j in range(y, y + n):
      if board[i][j] != board[x][y]:
        return False
  return True
  #######################  ############################

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

 

시간소요가 44ms 에서 40ms로 줄었다.

 

 

###########################

 

정리하니 보기도 좋고 깔끔하다 ! 만족 X )