[백준/Baekjoon] 1992 쿼드트리 C++ :: Divide and conquer

 

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

1992번: 쿼드트리

---

1. Logic

4등분을 해서 모든 칸이 일치하면 해당 칸의 번호를 출력하는 문제이다. 기본적인 분할 정복 문제이지만 출력을 할 때 한번 생각해야 되서 실버 1인듯?하다

 

기본적인 분할 정복 아이디어를 활용하여 풀이하면 되고, 출력은 분할하는 부분에서 즉 섞여있는 부분을 확인하려고 재귀를 들어갈 때 '('를 출력하고 들어가서 확인하고 나오면서 ')'를 출력해주면 된다.

---

2. Code

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

string input[65];

void solve(int y, int x, int size) {
    bool check = false;
    for(int i = y; i < y+size; i++) {
        for(int j = x; j < x+size; j++) {
            if(input[y][x] != input[i][j]) {
                check = true;
                break;
            }
        }
        if(check) break;
    }
    
    if(check) {
        cout << '(';
        solve(y, x, size / 2);
        solve(y, x + size/2, size / 2);
        solve(y + size/2, x, size / 2);
        solve(y + size/2, x + size/2, size / 2);
        cout << ')';
    }
    else {
        cout << input[y][x];
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> input[i];
    }
    
    solve(0, 0, n);
}

 

 

---

 

 

3. Feedback

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐