[알고리즘][Python] 백준 1992 쿼드트리 문제 풀이

문제 출처 : www.acmicpc.net/problem/1992

1992번: 쿼드트리

---

문제 해석 : 0 또는 1로만 이루어진 구역을 찾는 것으로 다른 숫자가 섞여 있다면 이를 4분할 해서 다시 한 번 검사하는 문제이다.

 

문제 풀이 : 전형적인 분할정복 문제로 재귀적으로 함수를 사용하여 풀 수 있다. 

---

풀이 코드

def check(arr):
    length = len(arr)

    first = arr[0][0]

    for i in range(length):
        for j in range(length):
            if arr[i][j] != first:
                return False
    return True

def solution(arr):

    if check(arr):
        if arr[0][0] == 0:
            print(0, end ="")
        else:
            print(1, end="")
    else:
        temp = []
        cut = len(arr) // 2
        print("(", end = "")
        for i in range(2):
            start = i * cut
            end = (i+1) * cut
            new_arr = arr[start:end]

            for j in range(2):
                start_2 = j * cut
                end_2 = (j+1) * cut

                for element in new_arr:
                    temp.append(element[start_2:end_2])

                solution(temp)
                temp = []
        print(")", end = "")

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

solution(arr)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.