[BOJ/백준 2630][C++] 색종이 만들기

문제

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

백준 2630

백준 2630

 

문제 내용

주어진 입력에서 색종이 개수를 구하는 문제이다.

색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반으로 나누어 다시 확인을 해야 한다.

 

문제 풀이

문제에서 나와있는 대로, n/2를 해나가면 되기 때문에 분할정복 개념이 쓰였다.

만약 범위 내의 칸이 모두 같은 색이 아니라면, 범위를 4 분할하여 다시 탐색하면 된다.

같은 행동을 범위만 다르게 해서 반복하기 때문에, 재귀 함수로 구현하면 된다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int arr[128][128];
int n, white, blue;

// 범위 내의 칸들이 모두 같은 색인지 판단하는 함수 (기준은 num)
bool checkBox(int num, int sr, int sc, int er, int ec) {
    for (int i = sr; i < er; i++) {
        for (int j = sc; j < ec; j++) {
            if (num != arr[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void solution(int sr, int sc, int len) { //시작 좌표와 길이를 입력받음
    if (len == 0) // 종료 조건
        return;

    if (!(sr >= 0 && sc >= 0 && sr + len <= n && sc + len <= n)) //범위 체크
        return;

    if (checkBox(arr[sr][sc], sr, sc, sr + len, sc + len)) {
        // 범위 내의 칸들이 모두 같은 색이면 blue or white 늘리기
        arr[sr][sc] ? blue++ : white++;

    } else {
        len /= 2;
        solution(sr, sc, len);             // 좌측 위
        solution(sr + len, sc, len);       // 좌측 아래
        solution(sr, sc + len, len);       // 우측 위
        solution(sr + len, sc + len, len); // 우측 아래
    }
}

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

    solution(0, 0, n);
    cout << white << '\n' << blue;
}

 

문제 코드 설명

재귀 함수이기 때문에 종료조건을 반드시 설정해주어야 한다. (len==0일 때 종료)