백준 2630번 : 색종이 만들기

  한 영역 안에 있는 종이의 색이 같지 않다면 4등분을 하는 문제다. 다행히도 전체 종이의 한 변의 길이가 항상 2^k인 형태이기 때문에 등분을 했을 때 항상 깔끔하게 떨어지는게 보장된다. (만약 한 변의 길이가 7이였다면 4등분 자체를 할 수 가 없다.)

 

  그렇다면 내가 판정해야 할 제일 중요한 요소는 N*N의 이차원 Array 안의 원소가 모두 동일한 색인가?이다. 이것만 따로 코드로 옮겨보면 다음과 같다.

void check(int size, int startX, int startY)
{
    int target = arr[startX][startY];
    
    for(int x = startX; x < startX + size; x++)
    {
        for(int y = startY; y < startY + size; y++)
        {
            if(arr[x][y] != target)
            {
                // 다른 색의 종이가 발견됐습니다.
                
                return;
            }
        }
    }
    
    // 모두 같은 색입니다.
}

• size : 체크할 정사각형의 한 변의 길이
• startX : 체크를 시작할 X 위치
• startY : 체크를 시작할 Y 위치

  체크를 시작할 위치의 색을 target에 저장하고 이중 for문을 돌면서 단 하나라도 target과 다르다면 다른 색이 발견된 것이다. 따라서 다른 색의 종이가 발견됐을 경우에는 size를 반으로 줄여서 4등분한 구간을 각각 따로 다시 체크해주면 된다.

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int arr[129][129];
int w;
int b;

void check(int size, int startX, int startY)
{
    int target = arr[startX][startY];
    
    for(int x = startX; x < startX + size; x++)
    {
        for(int y = startY; y < startY + size; y++)
        {
            if(arr[x][y] != target)
            {
                check(size/2, startX, startY);
                check(size/2, startX + size/2, startY);
                check(size/2, startX, startY + size/2);
                check(size/2, startX + size/2, startY + size/2);
                
                return;
            }
        }
    }
    
    if(target == 0) w++;
    else b++;
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n ; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    check(n, 0, 0);
    
    cout << w << "\n" << b;
}