[파이썬] 백준 1992 : 쿼드트리 (실버1)

[파이썬] 백준 1992 : 쿼드트리 (실버1)

 

1992번: 쿼드트리

---

문제

---

풀이

0.방향성 생각

탐색하면서 기준점이랑 다른게 하나라도 나올경우 재귀 호출한다.

괄호의 경우에는 현재 탐색하는 영역에서 기준점과 다른게 하나라도 나올경우 괄호를 열고 탐색하고 괄호를 닫아준다.

0.방향성 생각

1. 전체코드

 

import sys
input = sys.stdin.readline

n = int(input())
arr = []
answer = ''
for i in range(n):
    arr.append(list(input()))

def solution(x,y,N) :
    global answer
    color = arr[y][x]
    d = N//2
    for i in range(y,y+N) :
        for j in range(x,x+N) :
            if color != arr[i][j] :
                answer += '('
                solution(x,y,d)
                solution(x+d,y,d)
                solution(x,y+d,d)
                solution(x+d,y+d,d)
                answer += ')'
                return 
    answer += color
solution(0,0,n)
print(answer)

 

코멘트

괄호가 언제 열리고 닫히는지만 잘 알면 쉽게 풀 수 있다.