[알고리즘] 백준 1992

백준 1992번 쿼드트리

해결 과정 요약

정사각형을 왼쪽위(left top), 오른쪽위(right top), 왼쪽아래(left bottom), 오른쪽아래(right bottom) 순서로 쪼개가면서 탐색하는 문제이다. 부분 정사각형 전체가 같은 수로 이루어져 있다면 하나의 출력으로 퉁치게 된다. 따라서 재귀함수를 이용한 DFS로 문제를 풀어보았다. 재귀함수를 호출하면서 string을 완성하는식으로 구현했다. 내부가 "0000"이나 "1111"이라면 "0" 또는 "1"로 바꿔준다. 아니라면 앞뒤에 괄호를 추가해주면 된다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N;
string s;
int a[100][100];

string dfs(int ly, int lx, int ry, int rx){
    if(ly+1 == ry && lx+1 == rx){
        if(a[ly][lx] == 0) return "0";
        else return "1";
    }
    else{
        string lt = dfs(ly, lx, (ry+ly)/2, (rx+lx)/2);
        string rt = dfs(ly, (rx+lx)/2, (ry+ly)/2, rx);
        string lb = dfs((ry+ly)/2, lx, ry, (rx+lx)/2);
        string rb = dfs((ry+ly)/2, (rx+lx)/2, ry, rx);
        if(lt+rt+lb+rb == "0000") return "0";
        else if(lt+rt+lb+rb == "1111") return "1";
        else{
            return "(" + lt + rt + lb + rb + ")";
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> s;
        for(int j=0; j<N; j++){
            a[i][j] = s[j]-'0';
        }
    }
    cout << dfs(0,0,N,N);
    
    return 0;
}

트러블슈팅

• 난해한 출력값
  • 겉보기에 출력값을 만들기가 어려워 보였으나 재귀함수를 이용하여 차근차근 만들어가면 간단했다.
• int 와 string
  • 처음에 dfs함수의 리턴타입을 int형으로 했으나 출력값을 만들기가 까다롭다는 것을 알고 string으로 바꿔서 생각해보니 쉬웠다.

코멘트

그래프 알고리즘과 재귀함수 활용, 그리고 문자열처리까지..
영양가있는 급식st