[백준알고리즘] 1992번: 쿼드트리-Python

[백준알고리즘] 1992번: 쿼드트리-Python

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

1992번: 쿼드트리

 

쿼드 트리에 대해서 잘 몰라서 먼저 찾아보았다. 아래 링크들을 통해서 확인하면 될 것 같다.

https://en.wikipedia.org/wiki/Quadtree

https://blog.naver.com/namsikie/60127442593

http://pigbrain.github.io/datastructure/2016/01/01/QuadTree_on_DataStructure

 

보니까 4개의 child로 데이터를 압축해서 표시시킴으로써 트리의 빠른 search의 특징을 더 활용하기 위한 방법인 듯하다.

 

 

일단은 문제를 풀기 위해서는 4가지 child의 구분을 해야 한다.

1. 왼쪽 위

2. 오른쪽 위

3. 왼쪽 아래

4. 오른쪽 아래

 

각 partition에 대한 처리는 같기 때문에 함수를 만들어서 재귀 처리를 해줄 것이다. 모두 같다면 같은 내용 1 또는 0이 나올 것이고, 모두 같지 않다면 또다시 4개의 자식들을 조사해서 구성하게 될 것이다.

 

따라서 각 partition마다 독립적이면서 다른 sub problems에 영향을 끼치지 않기 때문에 분할 정복법을 활용한 문제가 되겠다.

 

 

문제를 풀기 위한 아이디어를 코딩하는 것은 쉬웠다. 그런데 뜬금없이 틀려서 헤매었던 게 괄호였다...

2

00

00

일 경우에는 결과가 (0)이 아니라 0이 나와야 한다.

 

그 밖에는 쉬운 것 같다.

 

문자열을 합칠 때에는 리스트로 받아서 ''.join(list)가 대부분 추천하는 방식인 듯해서 사용해봤다.

import sys

N = int(sys.stdin.readline())
matrix = []
result = []

for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().strip())))


def quadtree(start_x: int, start_y: int, n: int):
    temp = matrix[start_x][start_y]
    rtn = []
    for i in range(n):
        for j in range(n):
            if temp != matrix[start_x + i][start_y + j]:
                rtn.append("(")
                rtn.extend(solve(start_x, start_y, n))
                rtn.append(")")
                return rtn

    return [str(temp)]



def solve(start_x: int, start_y: int, n: int):
    result = []
    result.extend(quadtree(start_x, start_y, n//2))
    result.extend(quadtree(start_x, start_y + n//2, n//2))
    result.extend(quadtree(start_x + n//2, start_y, n//2))
    result.extend(quadtree(start_x + n//2, start_y + n//2, n//2))
    return result


result.extend(quadtree(0, 0, N))
print(''.join(result))

 

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다