쿼드트리 [백준 1992] - python

import sys
input = sys.stdin.readline

def BOJ1992() :
  global graph
  
  def check(x, y, step) :
    flag = True
    pivot = graph[x][y]
    
    for i in range(x, x + step) :
      for j in range(y, y + step) :
        if graph[i][j] != pivot :
          flag = False
          break
    
    if flag == False :
      print("(", end='')
      step //= 2
      check(x, y, step)
      check(x, y+step, step)
      check(x+step, y, step)
      check(x+step, y+step, step)
      print(")", end='')
    elif pivot == '1' :
      print(1, end='')
    else :
      print(0, end='')
    
  N = int(input())
  step = int(N)
  
  graph = []
  for _ in range(N) :
    graph.append(list(input().rstrip()))
  
  check(0, 0, step)

BOJ1992()

 

접근 방법 :

1. 분할 정복으로 해당 문제를 정복하자 

2. 탐색 범위의 모든 값이 같다면 값을 출력해주고 아니면 다시 분할을 들어간다.

3. 분할을 들어갈때 탐색범위는 이전의 절반으로 계속 탐색해 들어간다.

 

장애물 이였던 것 :

1. 같은 유형의 문제를 몇번 풀었는데 왜 이문제는 새로웠을까...... 좀 더 정진하자

2. 재귀가 좀 더 익숙해져야 할것 같다.

 

 

 

 

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

1992번: 쿼드트리