백준 No.2603 [색종이 만들기]

// Baekjoon Online Judge No.2630 [색종이 만들기]

---

   Code   

#include <iostream>
#include <vector>
#define DEVIDING_STANDARD 2
 
using namespace std;
 
int N;
vector<vector<int>> paper;
// 1 is blue, 0 is white
 
int blue = 0;
int white = 0;
 
void DC(int len, int x, int y) { // len 길이의 block이 들어왔고, 이제 곧 쪼갤거다. (길이가 1일때 제외)
    if (len == 1) { // 더이상 나눌 수 없을 때
        if (paper[y][x]) blue++;
        else white++;
 
        return;
    }
 
    int div = len / 2;
    int initial_color = paper[y][x];
    int yVal = y, xVal = x;
 
    for (int j = yVal; j < yVal + len; j++) {
        for (int i = xVal; i < xVal + len; i++) {
            if (paper[j][i] != initial_color) goto devide; // 쪼개야 하므로 쪼개는 for문으로 gogo!
            if (j == yVal + len - 1 && i == xVal + len - 1) { // 현재 block에 color가 다 똑같을 경우
                if (initial_color) blue++;
                else white++;
 
                return;
            }
        }
    }
    
    devide:
 
    for (int j = 0; j < DEVIDING_STANDARD; j++) { // 쪼개는 for문
        for (int i = 0; i < DEVIDING_STANDARD; i++) {
            DC(div, x + div * i, y + div * j); // devide it
        }
    }
}
 
/* normal devide and conquer 는 1 조각까지 쪼개버리지만
 * 이 문제에서는 쪼개지 않는 조건이 필요.
 *    -> 한 block 이 same color 일때.
 */
 
int main() {
    cin >> N;
    paper.assign(N, vector<int>(N, 0));
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];
 
    DC(N, 0, 0);
 
    cout << white << '\n' << blue;
}

---

   How to solve   

  기존 분할 정복 문제의 형태에 더이상 쪼개지지 않을 조건 을 부여해야하는 문제였다. 또한 이 문제에서 더이상 쪼개지지 않을 조건은, 한 블럭에 해당하는 종이들의 색상이 모두 똑같은 경우이다. (이 문제에서 한 블럭의 크기는 2*2, 4*4, 등등이 될 수 있다.) 

 

  DC 함수에 입력되는 변수들에는 현재 탐색하는 블럭의 길이 ( initial_color ), 탐색을 시작할 좌표 ( int x, int y ) 가 들어가있다. 이 정보들을 토대로 현재 DC함수 내에서 체킹할 영역을 알 수 있을 것이다. 26번째 ~ 38번째 line에서 그 체킹할 영역에 해당하는 색종이의 색들이 다 같은지 아닌지 검사를 한다. 처음에 입력되는 변수인 x, y 값을 활용하여 첫 좌표의 색종이 색 변수를 만든다. (23번째 line 에  int initial_color; ) for문을 계속 돌면서 하나하나 해당 위치에 해당하는 색종이의 색이  initial_color  와 다른지 검사를 한다.

 

  만약 검사 도중 initial_color 와 다른 부분이 하나라도 발견이 되면 28번째 line에 따라 38번째 line에 있는 devide: 로 goto 한다. 체킹하던 영역의 색종이들의 색이 전부 같지 않다는걸 알게됐으니 쪼개야하기 때문이다.

 

  29번째 ~ 33번째 line은 for문을 돌면서 28번째 line에 한번도 걸리지 않고 for문의 끝자락까지 왔을때의 경우이다. 즉 체킹하던 영역의 색종이들의 색이 모두 같을때를 의미한다.  initial_color  를 토대로  initial_color 의 색이 즉 현재 영역의 색종이들의 색일 것이므로  initial_color  가 1인 경우 (파랑색)  blue++;  를,  initial_color  가 0인 경우 (흰색)  white++;  를 해준다. 그 후 더이상 쪼갤 필요가 없으므로  return;  을 진행한다. 그러면 이제 더이상 쪼개지 않고 이전에 쪼개던 영역을 쪼개기 시작할 것이다.