1992번: 쿼드트리

쿼드트리 

 

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

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

예제 입력 1 

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 

((110(0101))(0010)1(0001))

 

---

풀이

 

문제를 확인해보자.

 

1. N*N 배열에 흰 점을 나타내는 "0", 검은 점을 나타내는 "1"이 있다.
2. N*N 배열이 모두 0으로 되어있으면 압축 결과는 "0", 모두 1으로 되어있으면 압축 결과는 "1"이다.
3. 0과 1이 섞여있다면 바로 압축하지 못하고, 4개의 조각으로 쪼개어 다시 압축한다.
4. 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

 

 

---

설계

 

이 문제를 해결하기 위해 생각한 알고리즘은 분할 정복이다.

N*N 크기의 배열이 모두 0인지, 1인지를 판단하고 0과 1이 섞여있다면 4구역으로 나누어 다시 탐색해야 한다.

 

결국 0과 1이 섞어있다면, 나눌 수 있을 때까지 계속 4구역으로 나누며 모두 0 또는 1로 구성되어 있는지 확인하면 된다.

 

여기서 관건은 괄호이다. 

압축한 결과를 순서대로 괄호에 넣어서 출력해야 하는데, 이걸 어디서 처리해야 하는지 찾는 것이 중요하다. 

 

 

이 문제를 풀기 위해 고려할 점은,

 

1. 배열이 모두 같은 색인지 판단
2. 같은 색이라면 -> 0과 1 출력
3. 다른 색이라면 -> 4구역으로 나눠 다시 탐색
4. 괄호 처리

---

구현

 

위의 설계를 바탕으로 코드를 구현해보자.

 

1. 배열이 모두 같은 색인지 판단

 

• 첫 위치의 color를 저장하고 arr배열과 color의 값을 비교한다.
• 탐색하는 중 color가 같다면 -> true, 다르다면 false

 

 

2. 같은 색이라면 -> 0과 1 출력

 

• arr배열의 값이 0이라면 값에 "0" 추가
• arr배열의 값이 1이라면 값에 "1" 추가

 

 

3. 다른 색이라면 -> 4구역으로 나눠 다시 탐색

 

분할된 구역

 

• x, y => 제 2사분면
• x, y + size/2 => 제 3사분면
• x + size/2, y =>  제 1사분면
• x + size/2, y + size/2 => 제 4사분면

 

 

4. 괄호 처리

 

• "(" 는 color와 arr배열의 값이 다른 경우, 즉 구역안에 0과 1이 섞여서 존재하는 경우
• 4구역으로 나누는 경우에 출력

 

 

• ")"는 color가 달라 4구역을 나눠 탐색한 경우
• 4구역으로 나눠 재귀호출을 한 후에 출력

 

---

전체코드

 

let N = Int(readLine()!)!

var arr : [[Int]] = []

for _ in 0..<N {
    let Input = Array(readLine()!).map {Int(String($0))!}
   
    arr.append(Input)
}

var result = ""

divide(0,0,N)

func divide (_ x:Int , _ y: Int, _ size: Int){
    
    if check(x, y, size){
        if arr[x][y] == 0{
            result = result + "0"
        }
        else{
            result = result + "1"
        }
        
    }
    else{
        let sx = [ x, x, x + size/2, x + size/2 ]
        let sy = [y, y + size/2, y, y + size/2 ]

        for i in 0..<4{
            divide(sx[i], sy[i], size/2)
        }
        result = result + ")"
    }
}

func check (_ x: Int, _ y: Int, _ size: Int) -> Bool{
    
    let color = arr[x][y]
    
    for i in x..<(x + size){
        for j in y..<(y + size){
            if arr[i][j] != color {
                result = result + "("
                return false
            }
        }
    }
    return true
}

print(result)

 

 

---

정리

 

쿼드트리 문제는 나눌 수 있을 때까지 나누며 탐색하는 문제로 분할정복을 사용하는 알고리즘이다. 

 

이전에 풀었던 색종이 만들기 문제의 변형 문제같다. 

 

2630번: 색종이 만들기