[PS 백준 - 4.1] 1780번: 종이의 개수

문제 정보

백준 1780번 - 바로가기

• 난이도: 실버 2
• 알고리즘: 분할 정복

---

코멘트

※ 분할 정복 문제들은 재귀를 사용하기 때문에 divideConquer 라는 재귀함수를 정의하여 문제를 풀었다.

이 문제는 분할 정복을 처음 마주칠 때 풀기 좋은 문제인 것 같다. 이 문제를 풀면서 딱 이런게 분할 정복이구나!를 느낄 수 있었다.

1. 먼저 이차원 배열을 동적할당하여 맵을 만들고, 결과를 저장해둘 배열 result를 만들어두었다. (-1, 0, 1의 개수 저장)
2. 분할 정복 함수는 먼저 (starty, startx) 좌표에 있는 값을 저장하고, 이 좌표로부터 $n\times n$ 만큼 탐색을 하면서 값이 같은지 다른지를 확인한다.
3. 값이 모두 같으면 (starty, startx) 좌표에 있는 값의 개수를 1 증가시킨다.
4. 값이 하나라도 다르면 $3\times3$ 으로 영역을 쪼개서 각 영역마다 분할정복 함수를 재귀적으로 호출한다.

---

소스 코드

#include <iostream>
#include <cmath>

using namespace std;

void divideConquer(int**& arr, int n, int starty, int startx, int* result) {
    /*cout << "n: " << n << " y: " << starty << " x: " << startx << endl;
    cout << result[0] << " " << result[1] << " " << result[2] << endl;*/
    int store = arr[starty][startx];
    bool flag = false;


    for (int i = starty; i < starty+n; i++) {
        for (int j = startx; j < startx+n; j++) {
            if (arr[i][j] != store) {
                
                for (int a = 0; a < 3; a++) {
                    for (int b = 0; b < 3; b++) {
                        if (n > 1)
                            divideConquer(arr, n / 3, starty + ((n / 3) * a), startx + (n / 3) * b, result);
                    }
                }

                flag = true;
                break;
            }
        }if (flag) break;
    }
    if (!flag) {
        result[store + 1]++;
    }
}

int main() {
    int n;
    cin >> n;

    int** arr = new int* [n];

    for (int i = 0; i < n; i++) {
        arr[i] = new int[n];
    }

    int result[3] = { 0,0,0 }; // -1, 0, 1

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            arr[i][j] = a;
        }
    }

    divideConquer(arr, n, 0, 0, result);

    for (int i = 0; i < 3; i++) {
        cout << result[i] << "\n";
    }

    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
}