[BOJ][1780] 종이의 개수

1. 문제 링크

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

2. 사용 알고리즘

분할정복

3. 풀이

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

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

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

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

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

4. 소스 코드

4-1. C++

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

#include <iostream>

using namespace std;

int arr[2222][2222];
int ans[3]; // [0] : -1, [1] : 0, [2] : 1

void solve(int startRow, int startCol, int size) {
    int num = arr[startRow][startCol];
    int flag = 1;
    for (int i = startRow; i < startRow + size; ++i) {
        for (int j = startCol; j < startCol + size; ++j) {
            if (num != arr[i][j]) {
                flag = 0;
                break;
            }
        }
        if (!flag) break;
    }
    if (!flag) {
        solve(startRow, startCol, size / 3);
        solve(startRow, startCol + size / 3, size / 3);
        solve(startRow, startCol + (2 * (size / 3)), size / 3);
        solve(startRow + size / 3, startCol, size / 3);
        solve(startRow + size / 3, startCol + size / 3, size / 3);
        solve(startRow + size / 3, startCol + (2 * (size / 3)), size / 3);
        solve(startRow + (2 * (size / 3)), startCol, size / 3);
        solve(startRow + (2 * (size / 3)), startCol + size / 3, size / 3);
        solve(startRow + (2 * (size / 3)), startCol + (2 * (size / 3)), size / 3);
    }
    else {
        ++ans[num + 1];
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cin >> arr[i][j];
    }
    solve(0, 0, n);
    cout << ans[0] << "\n";
    cout << ans[1] << "\n";
    cout << ans[2] << "\n";
    return 0;
}

4-2. JAVA

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

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

public class Main {

    static int arr[][] = new int[2222][2222];
    static int ans[] = new int[3]; // [0] : -1, [1] : 0, [2] : 1

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        solve(0, 0, n);
        StringBuilder sb = new StringBuilder();
        sb.append(ans[0]).append("\n").append(ans[1]).append("\n").append(ans[2]).append("\n");
        System.out.println(sb);
    }

    public static void solve(int startRow, int startCol, int size) {
        int num = arr[startRow][startCol];
        int flag = 1;
        for (int i = startRow; i < startRow + size; ++i) {
            for (int j = startCol; j < startCol + size; ++j) {
                if (num != arr[i][j]) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 0) break;
        }
        if (flag == 0) {
            solve(startRow, startCol, size / 3);
            solve(startRow, startCol + size / 3, size / 3);
            solve(startRow, startCol + (2 * (size / 3)), size / 3);
            solve(startRow + size / 3, startCol, size / 3);
            solve(startRow + size / 3, startCol + size / 3, size / 3);
            solve(startRow + size / 3, startCol + (2 * (size / 3)), size / 3);
            solve(startRow + (2 * (size / 3)), startCol, size / 3);
            solve(startRow + (2 * (size / 3)), startCol + size / 3, size / 3);
            solve(startRow + (2 * (size / 3)), startCol + (2 * (size / 3)), size / 3);
        }else {
            ++ans[num + 1];
        }
    }
}