[백준] 1992번: 쿼드트리 (분할정복)

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

1992번: 쿼드트리

 

 

이 문제는 분할정복으로 접근해야 하는 문제이다.

 

풀이 방법은 다음과 같다.

1. 모두 0이나 1로 되어있지 않은 경우(조건이 만족하지 않은 경우) 4개로 쪼개서 다시 푸는 방식이다.

   조건이 만족하지 않는 경우 괄호 "("를 넣고, 4개로 쪼개고 나서 각 처리를 다 하고 나면, 다시 괄호 ")"를 넣는다.

2. 4개로 쪼개는 것은 재귀함수를 호출하여 풀고, 전달 인자로 그 사분면의 가장 왼쪽 위의 좌표와 크기를 넣는다.

3. 조건이 만족하는 경우(모두 0이나 1로 되어있는 경우)는 해당 색상의 값(0이나 1)을 출력해준다.

 

전체

순서대로 보여주는 과정

 

파이썬 풀이

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]

# devide and conquer 분할정복
def dnc(x, y, n):
    check = graph[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if check != graph[i][j]:
                check = -1
                break

    if check == -1:
        print("(", end='')
        n = n // 2
        dnc(x, y, n)  # 1사분면
        dnc(x, y + n, n)  # 2사분면
        dnc(x + n, y, n)  # 3사분면
        dnc(x + n, y + n, n)  # 4사분면
        print(")", end='')

    elif check == 1:
        print(1, end='')
    else:
        print(0, end='')


dnc(0, 0, n)