[BOJ][1992] 쿼드트리

1. 문제 링크

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

2. 사용 알고리즘

분할정복

3. 풀이

1) 시작점, 사이즈를 입력값으로 받는 solve 선언

2) 시작점에서 사이즈만큼 순회하며 동일한 값만 존재하는지 확인

3) 동일한 값만 존재하는 경우 해당 숫자의 종이 1개 존재

4) 동일하지 않은 값이 존재하는 경우 해당 종이를 4등분해서 순회

5) 2), 3), 4) 반복

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1992.cpp

#include <iostream>

using namespace std;

int arr[66][66];

void solve(int r, int c, int size) {
    int val = arr[r][c], flag = 1;
    for(int i = r; i < r + size; ++i) {
        for(int j = c; j < c + size; ++j) {
            if(arr[r][c] != arr[i][j]) {
                flag = 0;
                break;
            }
        }
        if(!flag) break;
    }
    if(flag) {
        cout << arr[r][c];
    } else {
        cout << "(";
        solve(r, c, size / 2);
        solve(r, c + size / 2, size / 2);
        solve(r + size / 2, c, size / 2);
        solve(r + size / 2, c + size / 2, size / 2);
        cout << ")";
    }
}

int main(void) {
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        string s; cin >> s;
        for(int j = 0; j < n; ++j) {
            arr[i][j] = s[j] - '0';
        }
    }
    solve(0, 0, n);
    cout << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1992.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[][] arr = new int[66][66];
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i) {
            String s = br.readLine();
            for(int j = 0; j < n; ++j) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }
        solve(0, 0, n);
        sb.append("\n");
        System.out.println(sb);
    }

    static void solve(int r, int c, int size) {
        int val = arr[r][c], flag = 1;
        for(int i = r; i < r + size; ++i) {
            for(int j = c; j < c + size; ++j) {
                if(arr[r][c] != arr[i][j]) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 0) break;
        }
        if(flag == 1) {
            sb.append(arr[r][c]);
        } else {
            sb.append("(");
            solve(r, c, size / 2);
            solve(r, c + size / 2, size / 2);
            solve(r + size / 2, c, size / 2);
            solve(r + size / 2, c + size / 2, size / 2);
            sb.append(")");
        }
    }
}