백준 2630] C++ 색종이 만들기

 

 

 

 

 

 

 

 

 

 

 

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

www.acmicpc.net/problem/2630

 

 

1. 문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고,

각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다.

주어진 종이를 일정한 규칙에 따라 잘라서,

다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서

<그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다.

나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면

같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다.

이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나,

하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를,

<그림 4>는 두 번째 나눈 후의 상태를,

<그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때

잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

예제 입력 1                      예제 출력 1

8                                                9

1 1 0 0 0 0 1 1                           7

1 1 0 0 0 0 1 1

0 0 0 0 1 1 0 0

0 0 0 0 1 1 0 0

1 0 0 0 1 1 1 1

0 1 0 0 1 1 1 1

0 0 1 1 1 1 1 1

0 0 1 1 1 1 1 1

2. 조건

1. 각 배열의 요소가 들어있는 칸을 기준으로 0 과 1의 갯수로 색종이를 구분한다.

2. (1 * 1), (2 * 2), (4 * 4), (8 * 8)일때 해당 정사각형의 모양에 같은 숫자가 들어있으면 그건 색종이 1개로 치부한다.

3. 위 조건일 때 0의 색종이와 1의 색종이의 갯수를 구하여라.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

int zero = 0;
int one = 0;

int divide(vector<vector<int>>& v, int x, int y, int h) {
    if (h == 1) {
        if (v[x][y] == 1) one++;
        else zero++;
        return v[x][y];
    }
    
    int num = 0;
    num += divide(v, x, y, h / 2);
    num += divide(v, x + (h / 2), y, h / 2);
    num += divide(v, x, y + (h / 2), h / 2);
    num += divide(v, x + (h / 2), y + (h / 2), h / 2);

    if (num == 4) {
        one -= 3;
        return 1;
    }

    if (num == 0) {
        zero -= 3;
        return 0;
    }

    return -100;
}

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N));

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%1d", &v[i][j]);

    divide(v, 0, 0, N);

    cout << zero << endl;
    cout << one << endl;
    return 0;
}

 

 

4. 풀이

이번에는 풀이가 뒤에 왔는데, 이게 보기 편할 것 같아서 이렇게 작성합니다.

 

해당 문제는 재귀를 이용한 분할정복으로 쉽게 풀 수 있는 문제입니다.

이와 비슷한 문제로 프로그래머스의 쿼드압축 후 개수 세기(programmers.co.kr/learn/courses/30/lessons/68936) 문제가 있습니다.

 

이 문제를 풀려면 재귀로 어떻게 접근하냐 입니다.

 

1차원 배열에서의 분할정복 같은 경우는 높이 없이, x 값과 y값을 가지고 분할정복을 할 수 있습니다.

 

void divide(vector<int> v, int x, int y) {
    if (x < y) {
        int mid = (x + y) / 2;
        divide(v, x, mid);
        divide(v, mid + 1, y);
    }
    else
        cout << x << " " << y << endl;
}

 

이런식으로 말이죠. Merge Sort를 생각하시면 됩니다.

 

하지만 2차원에 배열같은 경우 높이가 추가되면서 더 복잡해 짐니다.

해당 재귀 방법은 다음과 같습니다.

 

void divide(vector<vector<int>>& v, int x, int y, int h) {
    if (h == 1) {
        cout << x << " " << y << endl;
        return;
    }
    
    divide(v, x, y, h / 2);
    divide(v, x + (h / 2), y, h / 2);
    divide(v, x, y + (h / 2), h / 2);
    divide(v, x + (h / 2), y + (h / 2), h / 2);
}

 

즉 4번의 재귀가 필요하며, 재귀는 높이를 기준으로 나누면서 진행해야 합니다.

 

처음엔 이해가 잘 안되지만 출력 결과를 확인해보면서 생각해본다면 간단하게 풀립니다.

 

저같은 경우는 각 요소에 도착했을 때 0의 갯수와 1의 갯수를 새어준 후 해당 값을 return하도록 했습니다.

 

만약 1이 4개이거나 0이 4개라면 같은 색종이가 4개 있는 것이므로 총 개수에서 3개를 뺀 후,

다시 색종이 값을 return하는식으로 풀었습니다.

 

만약 1 = 2, 0 = 2 or 1 = 1, 0 = 3 이런식으로 색종이 결과가 나온다면 2개의 if문을 만족하지 않으므로,

바로 return -100을 해줌으로서 더이상 합처질 수 없다는 표현을 했습니다.