2630번: 색종이 만들기

[yeonddori]

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

문제 설명

N × N 크기의 종이가 주어지고, 이 종이는 0(흰색) 또는 1(파란색)으로 이루어져 있습니다. 이 종이를 계속해서 4등분하여 특정 영역이 모두 같은 색으로 이루어져 있는지를 확인하는 문제입니다. 만약 하나의 영역이 같은 숫자로 이루어져 있다면, 해당 색깔의 개수를 증가시키고 더 이상 분할하지 않습니다.

문제 풀이

우선, 입력값을 받아 paper 배열에 저장한 후, 주어진 종이를 9등분하면서 각 영역이 동일한 숫자로만 이루어져 있는지를 확인합니다.

• check 함수: 현재 영역이 하나의 숫자로만 이루어져 있는지를 확인합니다. 만약 하나의 숫자로만 이루어져 있다면 true를 반환하고, 아니라면 false를 반환합니다.
• divide 함수: 현재 영역이 하나의 숫자로만 이루어져 있다면 해당 숫자의 개수를 증가시키고, 아니라면 x, y 각각 크기를 2등분하여 재귀적으로 다시 검사합니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> paper;
int white = 0, blue = 0;

bool check(int x, int y, int size) {
    int color = paper[x][y];
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (paper[i][j] != color) return false;
        }
    }
    return true;
}

void divide(int x, int y, int size) {
    if (check(x, y, size)) {
        if (paper[x][y] == 0) white++;
        else blue++;
        return;
    }

    int new_size = size / 2;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            divide(x + i * new_size, y + j * new_size, new_size);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    paper.resize(N, vector<int>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> paper[i][j];
        }
    }

    divide(0, 0, N);
    cout << white << '\n' << blue;

    return 0;
}

후기

그동안 미뤄왔던 CLASS 3의 미해결 문제.. 날먹이다~ 호호