[백준] 1992 쿼드트리 (Python 파이썬)

문제 설명

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

1992번: 쿼드트리

위 링크의 문제 설명을 보고 문제를 이해하기 어려울 수 있는데, 한 구역안에 점들이 모두 같은 숫자로 이루어져있지 않으면 왼쪽 위-> 오른쪽 위-> 왼쪽 아래 -> 오른쪽 아래 순 (지그재그 모양)으로 나누어 나타낸다는 것을 이해하면 쉽다.

---

풀이 과정

이 문제는 큰 구역을 작은 구역으로 계속 쪼개어 나타내는 분할 정복 문제이다.

문제의 예시처럼, 다음과 같은 배열이 주어졌을 경우를 생각해보자.

11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

8 x 8 배열의 모든 원소가 0으로만 이루어지거나 1로만 이루어지지 않고, 0과 1이 섞여있으므로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 구역으로 나누어 다시 압축을 해야한다.

 

4개로 나눈 구역 중 왼쪽 위의 구역(4x4)은 그럼 다음과 같이 나타날 것이다.

1111
1111
0001
0001

마찬가지로 0과 1이 섞여있으므로 여기서 또 다시 구역을 나누어야 한다.

 

나눈 구역 중, 왼쪽 위와 오른쪽 위는 모두 1로만 이루어지게 되고

왼쪽 아래도 모두 0으로만 이루어지기 때문에 분할을 멈출 수 있으며

오른쪽 아래는 아직

01

01    이기 때문에 다시 한 번 구역을 나누어야 한다.

 

여기서 더 구역을 나누게 되면 한 구역의 크기는 1 (1x1)이 되므로 무조건 한 구역에는 한 숫자만 존재하게 된다.

 

따라서, 구역 나누기를 멈추면 된다.

 

이러한 방식으로 왼쪽 위 부터 오른쪽 아래 까지 검사를 해주면 된다.

이를 아래의 파이썬 코드로 구현하였다.

 

여기서, 재귀문을 실행하기 전에, 압축이 가능한 상태면

재귀문을 실행하지 않고 바로 끝낼 수 있도록 구현하였다.

 

재귀문 안에서, 0으로만 이루어지거나 1로만 이루어질 경우에만 answer배열에 0 or 1을 추가해주고

그렇지 않으면 계속 재귀문을 돌도록 하였다.

n = int(input())
graph = []
answer = []


def recursive(x, y, N):
    answer.append("(")
    for i in range(2):
        for j in range(2):
            count0, count1 = 0, 0
            tmpGraph = []
            for k in range(N):
                tmpGraph.append(graph[x + i * N + k][y + j * N:y + (j + 1) * N])
                if '0' in tmpGraph[k]:
                    count0 = 1
                if '1' in tmpGraph[k]:
                    count1 = 1

            if count0 == 1:
                if count1 == 1:
                    recursive(x + i * N, y + j * N, int(N / 2))
                else:
                    answer.append(0)
            elif count1 == 1:
                answer.append(1)

    answer.append(")")


contain0 = 0
contain1 = 0
for i in range(n):
    graph.append(list(input()))
    if '0' in graph[i]:
        contain0 = 1
    if '1' in graph[i]:
        contain1 = 1


if contain0 == contain1:
    recursive(0, 0, int(n / 2))
    for i in answer:
        print(i, end='')

else:
    if contain0 == 1:
        print(0)
    else:
        print(1)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !