[백준] 1992번 : 쿼드트리

문제

 

---

풀이

 

myunji.tistory.com/251

[백준] 2630번 : 색종이 만들기

이 문제와 유사한 문제이다.

 

분할을 하는 지점에서 괄호를 입력한다는 걸 깨달으면 문제 자체는 금방 풀린다.

---

소스코드

 

#include <iostream>

using namespace std;

int video[64][64];

bool isSame(int size, int row, int col, int color) {
    for (int i = row; i < (size + row); i++) {
        for (int j = col; j < (size + col); j++) {
            if (video[i][j] != color)
                return false;
        }
    }
    return true;
}

void divide(int size, int row, int col) {
    int color = video[row][col];

    if (isSame(size, row, col, color)) { //압축 가능
        cout << color;
    } else { //분할
        cout << '(';
        int resize = size / 2;
        for (int i = 0; i <= resize; i += resize) {
            for (int j = 0; j <= resize; j += resize)
                divide(resize, row + i, col + j);
        }
        cout << ')';
    }
}

int main() {
    int N;
    string temp[64];

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> temp[i];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            video[i][j] = temp[i][j] - '0';
    }
    divide(N, 0, 0);
}

2630번 문제와 다른 부분만 설명하도록 하겠다.

 

    int N;
    string temp[64];

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> temp[i];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            video[i][j] = temp[i][j] - '0';
    }

2630번과 똑같이 입력을 처리했다가 오류가 발생해 살펴보니 이 문제는 띄어쓰기 없이 입력이 들어오고 있었다.

그래서 일단 string 형식의 temp 1차원 배열에 입력을 저장하고, 하나하나 쪼개어서 video 배열에 넣어줬다.

 

void divide(int size, int row, int col) {
    int color = video[row][col];

    if (isSame(size, row, col, color)) { //압축 가능
        cout << color;
    } else { //분할
        cout << '(';
        int resize = size / 2;
        for (int i = 0; i <= resize; i += resize) {
            for (int j = 0; j <= resize; j += resize)
                divide(resize, row + i, col + j);
        }
        cout << ')';
    }
}

divide 함수만 약간 달라졌다.

isSame 함수에서 모든 색이 동일함을 확인하면 그 색을 출력하고, 분할하는 과정에서 앞뒤로 괄호를 붙여줬다.