[c++] 백준 1992: 쿼드트리 (분할정복)

재귀함수를 통해 풀이를 만들어주었다.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;

int n;
string str;

vector<string> img;

vector<string> to_sub(vector<string>& src, int dir) { // 반복되는 코드!!
    vector<string> result;
    int sz = src.size()/2;
    if(dir == 1) {
        for(int i=0; i<sz; i++) {
            result.push_back(src[i].substr(0, sz));
        }
    }
    else if(dir == 2) {
        for(int i=0; i<sz; i++) {
            result.push_back(src[i].substr(sz, sz));
        }
    }
    else if(dir == 3) {
        for(int i=sz; i<2*sz; i++) {
            result.push_back(src[i].substr(0, sz));
        }
    }
    else if(dir == 4) {
        for(int i=sz; i<2*sz; i++) {
            result.push_back(src[i].substr(sz, 2*sz));
        }
    }
    return result;
}

string dfs(vector<string> src) {
    string result;
    bool all_zero = true;
    bool all_bit = true;
    for(int i=0; i<src.size(); i++) for(int j=0; j<src.size(); j++) {
        if(src[i][j] == '0') all_bit = false;
        else all_zero = false;
    }

    if(all_zero) { return "0"; }
    if(all_bit) { return "1"; }

    vector<string> sub_str;

    sub_str = to_sub(src, 1); // 반복되는 코드!!
    result += dfs(sub_str);
    sub_str = to_sub(src, 2);
    result += dfs(sub_str);
    sub_str = to_sub(src, 3);
    result += dfs(sub_str);
    sub_str = to_sub(src, 4);
    result += dfs(sub_str);

    return "(" + result + ")";

}

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> str;
        img.push_back(str);
    }
    cout << dfs(img);
}

 

정답은 맞았지만 찝찝한 부분이 있었다. 반복되는 코드가 많다는게 마음에 들지 않았기 때문이다. 알고리즘 강의로 유명한 바킹독의 코드를 염탐했다. 

아이디를 검색하면 풀이를 염탐할 수 있다

 

코딩테스트는 고등학교 때 수학문제 푸는 것과 비슷하다. 문제를 맞출 순 있지만 답안지를 보면 도움이 된다. 바킹독의 코드가 내겐 답안지같은 존재다. 

 

답안지에 재귀함수의 파라미터로 x, y, sz를 받아주었다. 나는 vector<string>을 받은게 문제였다. 재귀함수 안의 재귀함수에서 argument를 만들면서 반복되는 코드의 원인이 되었기 때문이다. 그럼 파라미터를 변경해서 새로 코드를 작성해보자

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;

int n;
string str;
vector<string> img;

string dfs(int x, int y, int sz) {
    string result;
    bool all_zero = true;
    bool all_bit = true;
    for(int i=x; i<x + sz; i++) for(int j=y; j<y + sz; j++) {
        if(img[i][j] == '0') all_bit = false;
        else all_zero = false;
    }

    if(all_zero) { return "0"; }
    if(all_bit) { return "1"; }

    return "(" + dfs(x, y, sz/2) + dfs(x, y+sz/2, sz/2) + dfs(x+sz/2, y, sz/2) + dfs(x+sz/2, y+sz/2, sz/2) + ")";
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> str;
        img.push_back(str);
    }
    cout << dfs(0,0,n);
}

 

to_sub함수를 사용하지 않았기 때문에 훨씬 간결해진 것을 볼 수 있다. 

(추가로) 재귀함수의 재귀함수를 operator+ 연산을 통해 한줄로 표현해주었다. 코드가 가로로 길어졌긴 하지만 한줄표현이 마음에 든다.