[백준] 2630번 : 색종이 만들기

문제

 

---

풀이

 

전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다.

문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다.

 

이 문제도 색종이의 색이 모두 같을 때까지 색종이를 4등분하며 문제를 쪼개나가면 된다.

---

소스코드

 

#include <iostream>

using namespace std;

int paper[128][128];
int colors[2]; //colors[0] = white, colors[1] = blue

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

void divide(int size, int row, int col) {
    int color = paper[row][col];

    if (isSame(size, row, col, color)) { //종이의 색이 모두 같음
        colors[color]++;
    } else { //분할
        int resize = size / 2;
        for (int i = 0; i <= resize; i += resize)
            for (int j = 0; j <= resize; j += resize)
                divide(resize, row + i, col + j);
    }
}

int main() {
    int N;

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];
    }
    divide(N, 0, 0);
    cout << colors[0] << '\n' << colors[1] << '\n';
}

전체 소스코드다.

 

int paper[128][128];
int colors[2]; //colors[0] = white, colors[1] = blue

색종이의 상태를 저장할 2차원 배열과 흰 종이와 파란 종이의 수를 저장할 1차원 배열이다.

재귀함수를 호출할거라 둘다 전역변수로 선언했다.

흰 종이와 파란 종이를 int white, blue 이런식으로 저장하려다가 그냥 한번에 관리하려고 배열로 묶었다.

 

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

색종이의 색을 확인하는 isSame 함수이다.

divide 함수로부터 받아온 색종이의 제일 왼쪽 윗칸의 색을 기준으로 색종이의 모든 색이 같은지 확인한다.

for문의 범위를 헷갈리지 않도록 주의해야 한다.

 

void divide(int size, int row, int col) {
    int color = paper[row][col];

    if (isSame(size, row, col, color)) { //종이의 색이 모두 같음
        colors[color]++;
    } else { //분할
        int resize = size / 2;
        for (int i = 0; i <= resize; i += resize)
            for (int j = 0; j <= resize; j += resize)
                divide(resize, row + i, col + j);
    }
}

이 문제의 핵심이라고 할 수 있는 문제를 쪼개는 부분이다.

isSame 함수를 호출해 종이의 모든 색이 같은지 확인하고 그렇지 않다면 분할한다.

 

가로 세로 길이가 절반이 되니까 2로 나누어 resize에 저장했다.

그리고 resize*resize 크기의 종이 4개를 호출하는데, 왼쪽 위->오른쪽 위->왼쪽 아래->오른쪽 아래 순으로 호출될 것이다.

 

divide(resize, row, col);
divide(resize, row, col + resize);
divide(resize, row + resize, col);
divide(resize, row + resize, col + resize);

풀어쓰면 이와 같다.