BOJ - 쿼드트리(1992)

실버1 : 분할정복 문제이다.

처음에 너무 삽질했다.. 그냥 구조적으로 부족한 것 같다.

Code

//
//  main.cpp
//  algorithm_prac
//
//  Created by 최완식 on 2021/04/05.
//
 
#include <iostream>
#include <vector>
using namespace std;
int N;
int map[64][64];
vector<char> ans;
 
void go(int sy, int sx, int d){
    int setN = map[sy][sx];
    int flag = 0;
    for (int i = sy; i < sy+d; i++) {
        for (int j = sx; j < sx+d; j++) {
            if (setN != map[i][j]) {
                flag = -1;
                break;
            }
        }
        if (flag == -1) break;
    }
    
    if (flag == 0) ans.push_back(setN + '0');
    else {
        ans.push_back('(');
        
        go(sy, sx, d/2);
        go(sy, sx+d/2, d/2);
        go(sy+d/2, sx, d/2);
        go(sy+d/2, sx+d/2, d/2);
        
        ans.push_back(')');
    }
}
 
int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        char temp[64];
        cin >> temp;
        for (int j = 0; j < N; j++) {
            map[i][j] = temp[j] - '0';
        }
    }
 
    go(0, 0, N);
    for (int i = 0; i < int(ans.size()); i++) {
        cout << ans[i];
    }
    return 0;
}
 
 

Reference

• 백준(1992번) - 쿼드트리