백준 1992번 쿼드트리 - SWIFT

문제

---

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

 

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

출력

영상을 압축한 결과를 출력한다.

 

문제 링크

 

 

풀이

---

백준 1074번 Z 라는 문제와 거의 비슷한 문제인 거 같다.

영상이 전부 1인지 0인지를 먼저 검사하고, 만약 전부 1이나 0이 아니라면 4등분을 해서 똑같이 검사해주면 되는 문제다.

만약 전부 1이나 0이라면, 함수는 더 이상 탐색하지 않고 멈춘다.

대신 재귀함수가 4갈래로 진행되기 때문에, 한쪽이 전부 같다고 해도 다른 쪽이 전부 같지 않으면 함수는 다른 갈래로 계속 진행된다.

 

 

프로그램 동작

---

1. 가장 먼저 전체를 확인해본다.만약 하나라도 서로 다른 부분이 있다면 다음 단계로 넘어가고, 1이나 0으로 전부 같다면 1 또는 0만 출력한다.

괄호를 출력하면 안된다.

필자는 괄호를 출력했다가, 틀렸습니다가 나와서 어느 부분이 틀렸는 지 한참 고민했다...▼

 

 

2. 전부 같지 않았다면, 4등분을 하고 왼쪽 위부터 검사를 시작해본다.

4등분의 결과가 괄호 안에 담겨야하므로, 재귀함수가 4갈래로 갈라지기 전에 미리 괄호를 출력해놓는다.▼

 

 

3. 이번에도 전부 같지 않으므로, 또 4등분을 하고 왼쪽 위부터 검사한다.

이번 4등분의 결과도 괄호 안에 담겨야하므로, 재귀함수가 4갈래로 갈라지기 전에 미리 괄호를 출력한다.

이번 왼쪽 위는 전부 같으므로 괄호 다음에 1을 넣어 준다.▼

 

 

이제 방금 구간은 더 이상 쪼개지 않아도 된다.

다음 구간인 오른쪽 위와 왼쪽 아래도 확인해본다.

오른쪽 위 구간과 왼쪽 아래 구간도 전부 같으므로 1과 0을 순서대로 추가해준다.▼

 

 

하지만 오른쪽 아래 구간은 전부 같지 않으므로, 다시 4갈래로 쪼개준다.

이번 갈래도 괄호안에 담겨야하므로 괄호를 미리 넣어준다.

이번 갈래는 원소가 전부 하나이므로, 각 숫자를 넣어준다.

하지만 코드에서는 통일성을 위해 위에서 검사했던 방식을 똑같이 사용해줬다.

그리고 이번 구간은 마지막 구간까지 검사가 된 구간이므로 마지막에 괄호를 닫아준다.

따라서 (0101)이 들어가게 된다.▼

 

 

4. 3번에서 한 구간의 검사가 다 끝났으므로, 괄호를 닫아주고 다음 구간으로 넘어간다.

그리고 앞의 과정을 똑같이 해준다.

이번구간의 전체는 같지 않지만, 4등분을 하면 각 구간은 전부 같은 숫자로 들어가있게 된다.

따라서 (0010)을 넣어준다.▼

 

 

5. 4번에서의 구간 검사도 다 끝났으므로, 다음 구간으로 넘어간다.

이번 구간은 전부 같으므로, 괄호 없이 1을 추가해준다.▼

 

 

다음 구간으로 넘어간다.

 

 

6. 이번 구간은 4번 구간과 같이 전체가 같진 않지만, 4등분하면 각 등분의 요소들은 전부 같은 구간이다.

(0001)을 추가해준다.▼

 

 

7. 마지막 구간까지 다 돌았으므로, 괄호를 닫아준다.

그리고 지금까지 더한 문자열이 답이 된다.▼

 

 

구간만 4등분씩 나눠가며 검사하면 쉽게 해결할 수 있다.

 

 

Swift 코드

---

let N = Int(readLine()!)!
var M = Array(repeating: [String](), count: N)
var A = ""
for i in 0..<N {
    M[i] = readLine()!.map { String($0) }
}

func check(_ minY: Int, _ minX: Int, _ maxY: Int, _ maxX: Int) -> Bool {
    for i in minY..<maxY {
        for j in minX..<maxX {
            if M[minY][minX] != M[i][j] {
                return false
            }
        }
    }
    return true
}

func find(_ minY: Int, _ minX: Int, _ maxY: Int, _ maxX: Int) {
    if check(minY, minX, maxY, maxX) {
        A += M[minY][minX]
    } else {
        A += "("
        find(minY, minX, maxY - (maxY - minY) / 2, maxX - (maxX - minX) / 2)
        find(minY, minX + (maxX - minX) / 2, maxY - (maxY - minY) / 2, maxX)
        find(minY + (maxY - minY) / 2, minX, maxY, maxX - (maxX - minX) / 2)
        find(minY + (maxY - minY) / 2, minX + (maxX - minX) / 2, maxY, maxX)
        A += ")"
    }
}

find(0, 0, N, N)
print(A)