[Python] 백준 1992 쿼드트리 문제풀이 및 정답해설

 

문제 주소 : https://www.acmicpc.net/problem/1992

 

문제풀이

대표적인 분할정복 문제이다. 쿼드트리란, 비트를 압축하여 표현할 수 있는 트리의 구조를 의미한다고 한다.

본 문제의 설명을 보면 알 수 있듯, n*n 사이즈의 맵이 주어지면, 해당 맵을 (좌상단, 우상단, 좌하단, 우하단)으로 총 4개로 분해할 수 있다.

또한 분해되어 표현되는 부분은 괄호로 정리한다. 이는 트리의 상속과정을 나타낸다고도 이해할 수 있다.

(0(0011)(0(0111)01)1)

 

분할정복을 수행할 때, 맵을 나누는 방식도 중요하지만, 어떤 정보가 필요한지 문제에 따라 구상할 필요가 있다.

 

이번 문제에서 필요한 정보는, 우측 상단의 좌표값과 맵의 크기인 n이다.

매 분할과정에서 n은 2배수로 줄어든다.

nr, nc는 사분면의 위치에 따라서 다르다.

이 때 nr과 nc는 우측 상단의 좌표값을 의미한다.

 

위의 총 세가지 값을 알고 있어야 하는 이유는, 탐색 범위의 설정 때문이다.

쿼드트리를 생성하기 위한 탐색범위를 지정하고,

해당 범위에 같은 숫자가 반복되어 있는지에 대한 여부를 판단하기 위해선 범위가 필요하다.

 

해당 범위를 기반으로 재귀함수를 수행하면 되겠다 !

 

그렇다면, 분할정복의 분할 타이밍과 병합은 어떤식으로 설계해야 할까? 

쿼드트리는 n*n 범위 내에 모두 같은 숫자만 포함되어 있다면, 하나의 숫자로 표현할 수 있다.

 

그렇다면, 분할 타이밍은 탐색 범위 내에 서로 다른 숫자가 섞여있을 때 하면 되겠다.

 

그리고, 현재 맵을 4개로 분할하였을 때, 상속 구조를 유지하기 위해서, 4개의 분할된 맵은 하나의 괄호로 지정되어야 한다.

그렇다면, 병합 또한 4개의 맵으로 분할하고 나온 결과로 해주면 되겠다.

 

아래의 코드를 읽으면 더욱 쉽게 이해할 수 있을 것이다.

정답코드

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

def bfs(n, nr, nc):
    # 현재 영역이 모두 같은 값인지 확인
    first = graph[nr][nc]
    all_same = True

    for i in range(nr, nr + n):
        for j in range(nc, nc + n):
            if graph[i][j] != first:
                all_same = False
                break
        if not all_same:
            break

    # 만약 영역 내 모든 값이 같다면 해당 값 반환
    if all_same:
        return str(first)

    # 4개 영역으로 분할하여 탐색
    half = n // 2
    ans_1 = bfs(half, nr, nc)       # 좌상단
    ans_2 = bfs(half, nr, nc + half) # 우상단
    ans_3 = bfs(half, nr + half, nc) # 좌하단
    ans_4 = bfs(half, nr + half, nc + half) # 우하단

    return f'({ans_1}{ans_2}{ans_3}{ans_4})'

print(bfs(n, 0, 0))