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

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

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

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

1992번: 쿼드트리

 

풀이

분할정복의 기본적인 문제이다.

재귀를 이용하여 가장 작은 부분문제를 해결하는 것으로 전체의 문제를 해결 할 수 있었다.

 

1. 전체가 같은지 조건을 검사
2. 조건에 부합하지 않다면, 1 - 2 - 3- 4 분면으로 나누기
3. 나눠진 4분면들을 각각 검사
4. 조건에 부합하지 않다면, 1 - 2 - 3- 4 분면으로 나누기
5. 부분 문제가 가장 작은 문제가 되거나, 조건에 부합할때 까지 반복
6. 전체 문제의 해결

 

import sys
input = sys.stdin.readline


def DFS(y, x, n):
	# 가장 작은 단위
    if n == 1:
        print(maps[y][x], end="")
        return

	# 조건 검사
    for i in range(y, y+n):
        for j in range(x, x+n):
        	# 조건에 부합하지 않으면, 4분면으로 나눠서 검사
            if maps[y][x] != maps[i][j]:
                print("(", end="")
                DFS(y, x, n//2)
                DFS(y, x+n//2, n//2)
                DFS(y+n//2, x, n//2)
                DFS(y+n//2, x+n//2, n//2)
                print(")", end="")
                return
	# 조건 부합
    print(maps[y][x], end="")
    return


N = int(input())
maps = []
for _ in range(N):
    maps.append(list(map(int, list(input().rstrip()))))

DFS(0, 0, N)