[Python] 백준 1992 - 쿼드트리 [Silver1]

출처

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

풀이 전략

우선 문제를 이해하는게 먼저이다. 솔직히 말하면 이 문제 자체를 이해하는데 시간이 좀 걸렸다.
차근차근 읽어보면, 이 문제의 경우 정사각형 내부에 있는 수들이 모두 같은지를 판별해서 압축하는 내용이다. 그렇기 때문에 정사각형에 0만 있거나 1만 있지 않는 경우 사각형을 반으로 쪼개가면서 재귀적으로 조건문을 돌리면서 출력을 하면 된다.

풀이

먼저 예제를 보면, 8x8 size의 정사각형이 있는데 사각형 내부에 1또는 0만 있지 않는 경우 arr[x][y] != arr[i][j] 사각형을 4등분 해서 재귀적으로 실행을 하는데, 이 때 재귀를 들어가기 전 '('를 재귀를 나올 때 ')'를 append해서 재귀를 들어갔다는 표시를 남긴다.
자세한 풀이는 그림을 보고 이해하는게 더 빠를 것이다.

소스 코드

# Question: BJ 1992 (https://www.acmicpc.net/problem/1992)
# Rank: Silver1
# Algorithm: Divide and Conquer, Recursion

import sys
input = sys.stdin.readline

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

def quadtree(x, y, n):
    if n == 1:
        return str(arr[x][y]) # 1x1일 때는 그냥 반환
    result = []
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[x][y] != arr[i][j]: # 4등분한 사각형 중 하나라도 다른 숫자가 있으면
                result.append('(')
                result.extend(quadtree(x, y, n//2)) # 왼쪽 위 사각형
                result.extend(quadtree(x, y+n//2, n//2)) # 오른쪽 위 사각형
                result.extend(quadtree(x+n//2, y, n//2)) # 왼쪽 아래 사각형
                result.extend(quadtree(x+n//2, y+n//2, n//2)) # 오른쪽 아래 사각형
                result.append(')')
                return result
    return str(arr[x][y])

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

결과

참고

append vs extend

위의 소스코드를 보면 다음과 같은 부분이 있다.

result = []

...
result.append('(')
result.extend(quadtree(x, y, n//2))
...

result라는 list가 있고 append와 extend함수가 주어져 각각의 함수 안에 있는 결과값을 리스트에 집어 넣는다.
그렇다면 append와 extend는 무슨 차이가 있을까?

1. append

a = [1,2,3]
b = [4,5]

a.append(b)
print(a)
>>>
[1,2,3,[4,5]]

append의 경우, [4,5]를 하나의 원소로 보고 이 자체를 기존의 배열에 집어넣게 된다.

2. extend

a = [1,2,3]
b = [4,5]
a.extend(b)
print(a)
>>>
[1,2,3,4,5]

이렇게 extend 단어 뜻에 맞게 배열의 크기를 추가한 원소의 개수만큼 '연장'시킨 뒤 그 공간에 새로운 원소를 집어넣는 방법이 extend이다.

따라서 이 문제의 경우 quadtree함수를 재귀를 통해 얻은 결과를 append로 집어넣는 것 보다는 extend함수로 집어 넣는 것이 훨씬 효과적이라는 것을 알 수 있다. (어차피 (,)로 구분을 해주기 때문)