[백준] 1992번 쿼드트리 - (Python)

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

1992번: 쿼드트리

전형적인 분할정복 문제. 앞서 포스팅한 분할정복 문제와 크게 다르지 않습니다. 다만, 괄호를 열고 닫는 구현이 추가된 문제입니다. 이 부분만 해결해 준다면, 큰 어려움 없이 해결할 수 있었습니다. 문제는 모든 행렬이 동일한 값이 아니라면 4 분할이 되므로, 색종이 개수 구하는 문제와 동일합니다.

※ 고려사항

1. 입출력 구현

2. 분할정복 구현 + 괄호

---

1. 입출력 구현

2차원 배열을 공백으로 구분하여 입력받습니다. 또 마지막 압축된 크기를 출력할 배열을 만들어줍니다. 2차원 배열을 받는법은 그래프 문제에서 굉장히 많이 다루었기 때문에 생략하겠습니다. 자세한 설명은 제 블로그 그래프 파트를 참고해 주세요!

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 배열
matrix = [list(map(int, input().strip())) for _ in range(n)]

# 출력 배열
cnt = []

 

2. 분할정복 구현 + 괄호

가장 메인이 되는 부분입니다. 해당 문제를 이해하는데 사실 시간이 조금 걸렸습니다. 간단하게 언급하면, 해당 분할된 좌표가 모두 같은 숫자로 구성되지 않았다면 4 분할하는 것이 문제의 설명입니다.

이 부분을 이해했다면, 코드 구현은 그렇게 어렵지 않습니다. 다만, 괄호를 처리하는 것이 중요합니다. 해당크기가 같은 행렬끼리는 같은 괄호 안에 묶어야 합니다. 그렇기 때문에 분할되기 전에 괄호를 열고, 모든 함수가 다 종료되었을 경우 괄호를 닫습니다. 그렇게 되면 자연스럽게 재귀 완료와 함께 구문이 종료됩니다. 코드는 다음과 같습니다.

# 분할정복
def sol(x, y, n):

    # 해당 좌표값 설정
    grid = matrix[x][y]

    # 해당 값과 모든 행렬이 동일한지 비교
    for i in range(x, x + n):
        for j in range(y, y + n):

            # 다르다면 분할정복
            if grid != matrix[i][j]:

                # 괄호 추가
                cnt.append('(')
                sol(x, y, n//2)
                sol(x, y + n//2, n//2)
                sol(x + n//2, y, n//2)
                sol(x + n//2, y + n//2, n//2)
                # 모든 재귀 종료 후 괄호 닫기
                cnt.append(')')
                return

    # 1로만 채워지면 1 추가, 그렇지 않으면 0
    if grid == 1:
        cnt.append('1')
    else:
        cnt.append('0')

---

전체코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 배열
matrix = [list(map(int, input().strip())) for _ in range(n)]

# 출력 배열
cnt = []

# 분할정복
def sol(x, y, n):

    # 해당 좌표값 설정
    grid = matrix[x][y]

    # 해당 값과 모든 행렬이 동일한지 비교
    for i in range(x, x + n):
        for j in range(y, y + n):

            # 다르다면 분할정복
            if grid != matrix[i][j]:

                # 괄호 추가
                cnt.append('(')
                sol(x, y, n//2)
                sol(x, y + n//2, n//2)
                sol(x + n//2, y, n//2)
                sol(x + n//2, y + n//2, n//2)
                # 모든 재귀 종료 후 괄호 닫기
                cnt.append(')')
                return

    # 1로만 채워지면 1 추가, 그렇지 않으면 0
    if grid == 1:
        cnt.append('1')
    else:
        cnt.append('0')

# 출력
sol(0, 0, n)
for i in cnt:
    print(i, end='')

 

---

분할정복 문제를 최근 자주 연습하고 있습니다. 현재 단계에서는 큰 무리 없이 문제를 해결하고 있습니다. 다만, 더 높은 단계의 분할정복 문제도 구현 가능한지는 잘 모르겠습니다. 더 많은 연습으로 숙련해야 될 것 같습니다. 다른 어려운 문제 포스팅으로 돌아올게요~

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^