[백준/C++] 1992번 쿼드트리

문제 링크

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

 

풀이

영상 크기인 N과 0과 1로 표현된 영상의 점들이 주어진다.

 

풀이 과정 중 실수했던 점은 예제처럼 점이 입력되었을 때 아래과 같이 int형 배열에 넣으려고 했다 -_-; 이렇게 하는 경우 arr[i][j]에 11110000은 1111이 들어가게 되는데, 왜 1 1 1 1 0 0 0 0 으로 들어갈 것이라 생각하게 됐는지... 이것 때문에 몇 번 재제출을 하다가 깨닫게 되었다.

// 주어지는 영상의 점 입력
// 11110000
// 11110000
// 00011100
// 00011100
// 11110000
// 11110000
// 11110011
// 11110011

// 처음 작성한 코드
int** arr = new int*[N];
for(int i = 0; i < N; i++){
	arr[i] = new int[N];
    for(int j = 0; j < N; j++){
    	cin >> arr[i][j];
    }
}

 

실수를 알게 된 뒤에 아래와 같이 수정했다.

int N;
string line;
cin >> N;
    
arr = new int*[N];
for(int i = 0; i < N; i++){
    arr[i] = new int[N];
    cin >> line;
    for(int j = 0; j < N; j++){
    	arr[i][j] = line[j] - '0';
    }
}

 

영상을 압축하는 부분은 아래와 같이 해결했다.

1. 사각형이 0으로만 또는 1로만 이루어져 있는지 체크한다.

2. 0으로만 이루어져 있는 경우 0, 1로만 이루어져 있는 경우 1을 출력한다.

3. 0과 1이 섞여 있으면 작은 사각형 4개로 나누어서 1을 반복한다.

 

quad라는 이름의 함수로 구현했다. 조금이라도 연산 시간을 줄일 수 있을 것이라 생각하여 0과 1이 섞여 있는 경우에는, 사각형 크기가 2이면 바로 출력이 이루어지도록 했다.

void quad(int startX, int startY, int N){
     // 1. 0 또는 1로만 이루어져 있는지 체크한다.
    int sum = 0;
    for(int i = startX; i < startX + N; i++){
        for(int j = startY; j < startY + N; j++){
            sum += arr[i][j];
        }
    }
    
    // 2. 0으로만 이루어져 있으면 0, 1로만 이루어져 있으면 1을 출력한다.
    if(sum == 0){cout << 0; return;}
    else if(sum == N*N){cout << 1; return;}
    // 3. 0과 1이 섞여 있으면 작은 사각형 4개로 나누어 다시 체크한다.
    else if(N==2){
        cout << "(" << arr[startX][startY] << arr[startX][startY+1]
            << arr[startX+1][startY] << arr[startX+1][startY+1] << ")";
        return;
    }
    else{
        cout << "(";
        quad(startX, startY, N/2);
        quad(startX, startY + N/2, N/2);
        quad(startX+N/2, startY, N/2);
        quad(startX+N/2, startY+N/2, N/2);
        cout << ")";
    }
}

 

최종 제출

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

int** arr;

void quad(int startX, int startY, int N){
    int sum = 0;
    for(int i = startX; i < startX + N; i++){
        for(int j = startY; j < startY + N; j++){
            sum += arr[i][j];
        }
    }
    
    if(sum == 0){cout << 0; return;}
    else if(sum == N*N){cout << 1; return;}
    else if(N==2){
        cout << "(" << arr[startX][startY] << arr[startX][startY+1]
            << arr[startX+1][startY] << arr[startX+1][startY+1] << ")";
        return;
    }
    else{
        cout << "(";
        quad(startX, startY, N/2);
        quad(startX, startY + N/2, N/2);
        quad(startX+N/2, startY, N/2);
        quad(startX+N/2, startY+N/2, N/2);
        cout << ")";
    }
}

int main(){
    int N;
    string line;
    cin >> N;
    
    arr = new int*[N];
    for(int i = 0; i < N; i++){
        arr[i] = new int[N];
        cin >> line;
        for(int j = 0; j < N; j++){
            arr[i][j] = line[j] - '0';
        }
    }
    
    quad(0, 0, N);
}