[C++]백준 - 1992번 문제

1992번: 쿼드트리 (acmicpc.net)

1992번: 쿼드트리

 

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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

재귀로 풀어야하는 분할 정복문제입니다.

 

비디오의 길이(가로 혹은 세로 길이) = N,

비디오의 좌표 = (X, Y) 라고 할 때, 다음과 같은 과정을 거칩니다.

 

1. (1 < N)이면 4등분하여, 재귀함수에 넣는다.

2. (N == 1)이면 그 좌표의 영상 정보를 return 한다.

3. return된 4개의 결과물을 string타입으로 더해서 0000 혹은 1111인지 확인한다.

4. 0000 혹은 1111이라면, 각각 0 또는 1로 반환한다.

5. 0000 혹은 1111이 아니라면, 괄호로 감싸 결과값을 반환한다.

 

예를 들어) N = 4인 입력

 

0000

0010

1111

1111

 

이 들어왔다면,

1. 4등분한다.

2. N != 1이므로 다시 4등분한다.

3. (0,0) 지점에서 반환값으로 각각 0, 0, 0, 0이 반환되었으므로 0을 반환한다.

4, (2,0) 지점의 반환값으로 각각 0, 0, 1, 0이 반환되었으므로 (0010)을 반환한다.

5. 같은 과정을 거쳐 아래 두 지점 모두 각각 1, 1을 반환하게 된다.

6. 최종적으로 N=4일 때, 4등분 된 지점들의 반환 값이 각각 0, (0010), 1, 1 이므로 (0(0010)11)을 반환하면 된다.

 

마지막으로, 반환된 값을 출력해주기만 하면 됩니다.

 

 

코드

---

#include <iostream>
#include <string>
using namespace std;

char mov[64][64];	//영상 정보를 담음 (y, x)

string solution(int x, int y, int N)
{
    string result = ""; 
    if(N == 1)  
    {
        result += mov[y][x];
        return result;
    }
    
    // 4등분하여 재귀
    int half_N = N / 2;
    result += solution(x, y, half_N);
    result += solution(x + half_N, y, half_N);
    result += solution(x, y + half_N, half_N);
    result += solution(x + half_N, y + half_N, half_N);
    
    if(result == "1111" || result == "0000") 
    {
        result = result[0];
        return result;
    }
    else
    {
        result = "(" + result + ")";	//괄호로 감싸서 return
        return result;
    }
    
}


int main() 
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        for(int j = 0; j < N; j++) mov[i][j] = input[j];
    }
    cout << solution(0,0,N);
    
	return 0;
}

 

그 외

---

처음에는 mov 배열을 int로 받았었는데, 이 문제에서 크게 int를 활용할 일이 없어 char타입으로 바꾸었습니다.