[백준 1992번] 쿼드트리 풀이

1992번: 쿼드트리

 

한 변의 길이가 N(N은 2의 배수)이고 0과 1로 이루어진 정사각형이 주어졌을 때, 이를 압축하여 표현하는 문제이다. 압축하는 규칙을 정리해보면 다음과 같다.

 

1) 모든 요소가 0인 정사각형은 0을 출력한다.

 

 

2) 모든 요소가 1인 정사각형은 1을 출력한다.

 

 

3) 1과 0이 섞여있는 정사각형은 4등분 하여 ( 왼쪽 위 정사각형 값, 오른쪽 위 정사각형 값, 왼쪽 아래 정사각형 값, 오른쪽 아래 정사각형 값)을 출력한다. 

 

 

문제에서 제시한 예시에 대해 출력 값을 도출해보자.

설명을 위해 임의적으로 A번 정사각형의 왼쪽 위 정사각형 값을 A왼위, 오른쪽 위 정사각형 값을 A오위, 왼쪽 아래 정사각형 값을 A왼아, 오른쪽 아래 정사각형 값을 A오아 로 적었다.

 

1번 정사각형 - 전체 정사각형

 

문제에서 주어진 예시는 0과 1이 섞여 있으므로, 이를 4등분 하여 (1왼위, 1오위, 1왼아, 1오아) 를 출력해야 한다. 이때 왼쪽 위 정사각형은 모두 0으로, 오른쪽 아래 정사각형은 모두 1로 이루어져 있다. 따라서 출력 값은 (0, 1오위, 1왼아, 1) 이 된다.

 

1오위 = 1번 정사각형의 오른쪽 위 정사각형(2번 정사각형) 출력 값을 구해보면, 

 

2번 정사각형 - 1번 정사각형의 오른쪽 위 정사각형

 

0과 1이 섞여 있으므로 4등분 하여 (2왼위, 2오위, 2왼아, 2오아) 가 된다. 2번 정사각형의 왼쪽 위와 오른쪽 위 정사각형은 모두 0으로, 왼쪽 아래와 오른쪽 아래 정사각형은 모두 1로 이루어져 있다. 따라서 1오위 = (2번 정사각형의 출력 값) = (0011) 이 된다.

 

1왼아 = 1번 정사각형의 왼쪽 아래 정사각형(3번 정사각형) 출력 값을 구해보자.

 

3번 정사각형 -  1번 정사각형의 왼쪽 위 정사각형

 

0과 1이 섞여 있으므로 4등분 하면 (3왼위, 3오위, 3왼아, 3오아)가 된다. 3번 정사각형의 왼쪽 위, 왼쪽 아래 정사각형은 모두 0으로, 오른쪽 아래 정사각형은 모두 1로 이루어져 있다.  따라서 1왼아 = (3번 정사각형의 출력 값) = (0, 3오위, 0, 1) 이 된다.

 

3오위 = 3번 정사각형의 오른쪽 위 정사각형(4번 정사각형) 출력 값을 구해보자.

 

4번 정사각형 - 3번 정사각형 오른쪽 위 정사각형

 

0과 1이 섞여있으므로 4 등분하여 구하면, (4왼위, 4오위, 4왼아, 4오아) 인 (0111)이 된다.

 

재귀적인 과정을 정리해보면, 

1번 정사각형의 출력 값 = (0 1오위 1왼아 1)

1오위 = 2번 정사각형의 출력 값 = (0011)

1왼아 = 3번 정사각형의 출력 값 = (0 3오위 0 1)

3오위 = 4번 정사각형의 출력 값 = (0111) 이고,

 

이를 합치면 1번 정사각형의 출력 값은 (0(0011)(0(0111)01)1) 이 된다.

 

이를 코드로 표현하면, 

 

void solve(int row, int col, int size) {

    for (int r=row; r<row+size; r++) {
        for (int c=col; c<col+size; c++) {
            if (map[row][col] != map[r][c]) {

                printf("(");
                solve(row, col, size/2);
                solve(row, col+size/2, size/2);
                solve(row+size/2, col, size/2);
                solve(row+size/2, col+size/2, size/2);
                printf(")");
                return ;
            }
        }
    }
    printf("%c", map[row][col]);
    return ;
}

 

정사각형의 왼쪽 위 점의 좌표를 받아 모든 좌표가 같은 값을 가지고 있는지 확인하고, 그렇지 않으면 (왼쪽 위 정사각형의 값, 오른쪽 위 정사각형의 값, 왼쪽 아래 정사각형의 값, 오른쪽 아래 정사각형의 값)을 재귀적으로 출력한다. 만약 모든 값이 0이나 1로 같다면, 처음 값 map[row][col] 을 출력해주면 된다.

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

char map[64][64];

void solve(int row, int col, int size) {

    for (int r=row; r<row+size; r++) {
        for (int c=col; c<col+size; c++) {
            if (map[row][col] != map[r][c]) {

                printf("(");
                solve(row, col, size/2);
                solve(row, col+size/2, size/2);
                solve(row+size/2, col, size/2);
                solve(row+size/2, col+size/2, size/2);
                printf(")");
                return ;
            }
        }
    }
    printf("%c", map[row][col]);
    return ;
}

int main() {

    int N;
    scanf("%d", &N);
    memset(map, '0', sizeof(map));

    for (int i=0; i<N*N; i++)
        scanf(" %c", &map[i/N][i%N]);

    solve(0, 0, N);
    return 0;
}