[C++] 백준 2630번 : 색종이 만들기(분할 정복)

문제링크

2630번: 색종이 만들기

 

 

위처럼 입력이 주어졌을 때 아래처럼 변의 길이를 N/2씩 나누어 가며 흰색으로 만들어진 정사각형과 파란색으로 만들어진 정사각형의 개수를 출력해야한다.

 

문제를 보면 잘 알겠지만 대놓고 분할정복의 방법을 사용하라고 그림까지 주어져있다. 분할정복의 자세한 내용은 알고리즘 카테고리에서 다루도록하고 간단하게 설명하면 하나의 문제를 같지만 더 작은 문제로 나눈다음 작은 문제를 해결하고 결과를 합쳐서 하나의 결과가 나오도록하게 하는 전략이다.

 

분할정복을 문제에 적용해보면 한 변의 길이가 N/2인 정사각형이 흰색 또는 파란색의 정사각형을 만들지 못할 경우 변의 길이를 N/2로 나누어 다시 확인한다.(분할)

만약 한 변의 길이가 N/2인 정사각형이 전부 흰색 또는 전부 파란색으로 이루어져있다면 흰색종이의 개수, 파란색 종이의 개수를 더해주고 해당 스텝을 종료한다.(정복)

 

더 자세한 설명은 코드와 주석으로 설명하겠다. (혹시 의문이 있으시면 댓글 달아주세요!)

코드

#include <iostream>
using namespace std;
 
int n, white, blue;
bool board[129][129];
 
// x좌표, y좌표, 변의 길이 를 인자로 받음
void rec(int r, int c, int n) {
    if (n == 1) {
        if (board[r][c] == 1) {
            blue++;
        }
        else if (board[r][c] == 0) {
            white++;
        }
        return;
    }
 
    bool w = true;        // 모두 흰색인지 체크하는 flag
    bool b = true;        // 모두 파란색인지 체크하는 flag
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 하나라도 흰색이 아니면 탐색 stop -> 흰색종이 X
            if (board[r + i][c + j] != 0) {
                w = false;
                break;
            }
        }
        if (w == false) {
            break;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 하나라도 파란색이 아니면 탐색 stop -> 파란종이 X
            if (board[r + i][c + j] != 1) {
                b = false;
                break;
            }
        }
        if (b == false) {
            break;
        }
    }
 
    // b == true 이면 탐색한 면 모두 파란색임
    if (b == true) {
        blue++;
        return;
    }
    // w == true 이면 탐색한 면 모두 파란색임
    else if (w == true) {
        white++;
        return;
    }
    // 아니라면 4분할 하여 재탐색
    else {
        rec(r, c, n / 2);                    // 1사분면
        rec(r + n / 2, c, n/2);                // 3사분면
        rec(r, c + n / 2, n/2);                // 2사분면
        rec(r + n / 2, c + n / 2, n/2);        // 4사분면
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> board[i][j];
        }
    }
    
    rec(1, 1, n);
    cout << white << '\n';
    cout << blue << '\n';
    return 0;
}

메모

해당 문제를 보면 정답률이 거의 70%나 되는 문제지만 분할 정복이 익숙하지 않은 나에게는 어려웠던 문제다. 문제해결기법을 수강하다 분할정복의 개념과 이해가 부족한 것 같아 찾아 풀었던 문제다. 분할정복 카테고리의 문제를 조금 더 풀어보고, 더 좋은 코드 짜는 법을 공부해야겠다.

 

+추가 수정코드 -> 더 깔끔한 풀이(?)

#include <iostream>
using namespace std;
 
int n, white, blue;
bool board[129][129];
 
void rec(int r, int c, int n) {
    int cnt = 0;    // 색칠된 개수 저장
        
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[r + i][c + j] == 1) {
                cnt++;
            }
        }
    }
 
    // 0개면 모두 흰색
    if (cnt == 0) {
        white++;
        return;
    }
    // n*n개면 모두 파란색
    else if (cnt == n * n) {
        blue++;
        return;
    }
    // 분할정복
    else {
        rec(r, c, n / 2);
        rec(r + n / 2, c, n / 2);
        rec(r, c + n / 2, n / 2);
        rec(r + n / 2, c + n / 2, n / 2);
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> board[i][j];
        }
    }
    rec(1, 1, n);
 
    cout << white << '\n';
    cout << blue << '\n';
    return 0;
}