[Baekjoon] 1992. 쿼드트리(python)

1992번: 쿼드트리

 

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리라는 방법이 있습니다.

 

흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서

같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있습니다.

 

N x N 크기의 영상이 주어졌을 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하세요.

 

풀이

분할정복을 이용해 풀 수 있는 문제입니다.

1. 현재 사각형의 모든 색이 같은 색인 경우

2. 다른 색이 껴있는 경우

- 해당 사각형을 4개로 나눠서 다시 1번 시작

 

위와 같은 순서로 진행하면 압축된 결과를 얻을 수 있습니다.

그럼 각 단계별로 어떻게 구현하면 좋을지 봐보겠습니다.

 

1. 현재 사각형 내의 모든 색이 같은 색인가?

영상의 크기를 결정하는 N의 크기는 최대 64 * 64 입니다.

그냥 모든 칸을 다 확인해봐도 빠르게 수행할 수 있는 크기입니다.👍

 

따라서 이중 for문을 이용해 확인하도록 하겠습니다.

 

2. 다른 색이 있는 경우, 어떻게 4조각으로 나눌 것인가?

그림으로 봐봅시다. 각 구역을 구별하기 위해서는 어떤 데이터가 필요할까요?

저는 왼쪽위의 시작점과 각 구역의 크기만 있으면 가능하다고 생각합니다.😊

 

그래서 분할 정복 메서드에 시작점인 x,y와 크기인 size를 변수로 전달해보겠습니다.

 

코드

n = int(input())
board = [ input() for _ in range(n) ]

def solve(x, y, size):
  # 1. 전부 같은 색인지 검사
  state = board[x][y]
  isSame = True
  for i in range(x, x+size):
    for j in range(y, y+size):
      if board[i][j] != state:
        isSame = False
        break
    if not isSame:
      break
    
  if isSame: # 모든 칸이 같은 색
    return state
  
  result = '('
  # 분할정복
  nSize = size//2
  result += solve(x, y, nSize) # 왼쪽위
  result += solve(x, y+nSize, nSize) # 오른쪽 위
  result += solve(x+nSize, y, nSize) # 왼쪽아래
  result += solve(x+nSize, y+nSize, nSize) # 오른쪽아래
  
  return result + ')'

print(solve(0,0,n))