[백준,c++] 1780번 - 종이의 개수

문제

1780번: 종이의 개수

 

코드

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

int map[2188][2188];
bool visited[2188][2188];
int N;

int cnt[3];
bool check(int r, int c, int div){
    int cmp = map[r][c];
    for(int i=r; i<r+div; i++){
        for(int k=c; k<c+div; k++){
            if(map[i][k] != cmp) return false;
        }
    }
    return true;
}

void go(int r, int c, int div){
    if(check(r,c, div)){
        cnt[map[r][c] + 1] ++;
    }
    else{
        int size = div / 3;
        for(int i=0; i<3; i++){
            for(int k=0; k<3; k++){
                go(r+size*i, c+size*k, size);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>map[i][k];
        }
    }
    go(0,0,N);
    
    cout<<cnt[0]<<'\n'<<cnt[1]<<'\n'<<cnt[2];
}

 

풀이

분할 정복 문제입니다.
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

void go(int r, int c, int div){
    if(check(r,c, div)){	// 종이가 모두 같은 수로 되어있다면 갯수 카운팅
        cnt[map[r][c] + 1] ++;
    }
    else{	// 아니라면 자른다.
        int size = div / 3;
        for(int i=0; i<3; i++){
            for(int k=0; k<3; k++){
                go(r+size*i, c+size*k, size);
            }
        }
    }
}

사실상 위 로직이 문제의 핵심 로직이라고 할 수 있습니다.

• N이 3^k꼴로 주어지기 때문에 종이를 자르는 2번 연산이 수행될 때마다 3으로 나눈 크기만큼 자르게 됩니다.
• 그리고 행과 열을 각각 세 번씩 총 9번 반복하여 go(r+size*i, c+size*k, size); 형식으로 잘라주게 되면 됩니다.