[BOJ] 2630 색종이 만들기

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

2630번: 색종이 만들기

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

recursive

 

---------------------------------------------------풀이----------------------------------------------------

 

cut_paper() 함수를 재귀적으로 호출한다.

맨 왼쪽 위의 좌표와 종이의 한 변의 크기를 매개변수로 넘겨준다.

만약 이 종이의 색이 한 가지로 이루어졌다면, is_one_color()가 true일 것이고,

그 때 종이의 색이 흰색이면 white를, 파란색이면 blue를 1 증가시키고 종료한다.

is_one_color()가 false이면,

종이를 네 조각으로 잘라 함수를 다시 호출한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int map[200][200] = {0, };
int N;
int white = 0, blue = 0;

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

// 맨 왼쪽 위의 좌표, 한 변의 크기
void cut_paper(int x, int y, int n){
    // 종이가 한 가지로 이루어졌으면 종료
    if(is_one_color(x, y, n)){
        if(map[x][y] == 0){
            white++;
        }
        else{
            blue++;
        }
        return;
    }

    // 종이를 넷으로 잘라 다시 호출
    cut_paper(x, y, n/2);
    cut_paper(x, y+n/2, n/2);
    cut_paper(x+n/2, y, n/2);
    cut_paper(x+n/2, y+n/2, n/2);
}

int main(void){
    FASTIO;
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> map[i][j];
        }
    }

    cut_paper(0, 0, N);

    cout << white << "\n" << blue << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이전에 푼 종이를 자르는 문제와 유사하다. 그 때는 9개로 나누는 문제였다.

그 때는 queue를 이용해 계속 잘라야 하는 부분을 저장해 queue가 empty일 때까지 반복했는데,

그 방식보다는 이렇게 바로 재귀적으로 가는 것이 효율적이다.