C++[baekjoon] 2630번: 색종이 만들기

 

문제의 핵심은 주어진 색종이를 같은 색으로만 이루어진 작은 종이들로 쪼개고, 각각 몇 개가 나오는지 세는 것.
분할 정복으로 해결해봤다.

 

먼저, divConq라는 재귀 함수를 정의했다.
이 함수는 현재 보고 있는 영역이 한 가지 색으로 이루어져 있는지 확인한다.

1. 만약 모두 같은 색이라면, white 또는 blue 개수를 증가시키고 끝낸다.
2. 아니라면, 색이 섞여 있다는 뜻이므로 4등분 해서 다시 검사한다.

그렇게 해서 최종적으로 하얀색 종이와 파란색 종이의 개수를 출력하면 끝이다.

 

사실 난이도가 높지않은 문제지만 분할 정복을 처음 접하는 사람들에게 입문용으로 추천..!

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

int white=0, blue=0;

void divConq(vector<vector<int>>& paper, int x, int y, int N){
    int color=paper[x][y];
    bool isSame=true;
    for(int i=x; i<x+N; i++){
        for(int j=y; j<y+N; j++){
            if(paper[i][j]!=color){
                isSame=false;
                break;
            }
        }
        if(!isSame) break;
    }
    if(isSame){
        if(color==1) blue++;
        else white++;
    } else{
        int newN=N/2;
        divConq(paper,x,y,newN);
        divConq(paper,x+newN,y,newN);
        divConq(paper,x,y+newN,newN);
        divConq(paper,x+newN,y+newN,newN);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N; cin>>N;
    vector<vector<int>> paper(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> paper[i][j];
        }
    }
    divConq(paper,0,0,N);
    cout<<white<<'\n'<<blue<<'\n';
}

 

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