알고리즘 색종이만들기(C++)

1335 : 색종이 만들기

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 985회    시도횟수: 1877회   

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 

 

 

전체 종이의 크기가 N×N(N=2^k, 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로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

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

[Copy] 8 1 1 0 0 0 0 1 1 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

[Copy] 9 7

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

/**************************************************************     Problem: 1335     User: a132034     Language: C++     Result: Success     Time:4 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std; static int PAPER[2] = { 0, 0 }; // 흰색, 파란색 void dnc(int** map, int x, int y, int N); // map / x, y 시작지점, 가로세로 크기N bool isSameColor(int **map, int x, int y, int N); //같은 색상인지 확인    int main() {     int N;     int **map;     cin >> N;     map = new int*[N];     for (int i = 0; i < N; ++i)         map[i] = new int[N];        for (int i = 0; i < N; ++i)     {         for (int j = 0; j < N; ++j)         {             cin >> map[i][j];         }     }     //input end        dnc(map, 0, 0, N);        cout << PAPER[0] << endl << PAPER[1];     return 0; }    void dnc(int** map, int x, int y, int N) {     if (N == 1)     {         PAPER[map[x][y]]++;         return;     }        N /= 2; // 4등분 해줌.     int midX = N + x;     int midY = N + y;            //0~x/2 0~y/2     if (!isSameColor(map, x, y, N))         dnc(map, x, y, N);        //0~x/2 y/2~y     if (!isSameColor(map, x, midY, N))         dnc(map, x, midY, N);        //x/2~x 0~y/2     if (!isSameColor(map, midX, y, N))         dnc(map, midX, y, N);        //x/2~x y/2~y     if (!isSameColor(map, midX, midY, N))         dnc(map, midX, midY, N); }    bool isSameColor(int **map, int x, int y, int N) {     int color = map[x][y];        for (int i = x; i < x + N; ++i)     {         for (int j = y; j < y + N; ++j)         {             if (color != map[i][j])                 return false;         }     }     PAPER[color]++;     return true; }

전형적인 divide and conquer 문제. 

작은 부분부터 올라오는 방법을 처음에 생각해 봤지만 큰 부분을 네가지 부분으로 나누어 공략하는게 더 d&c에 맞는 것 같아 그렇게 해결.

dnc 함수는 각 부분을 나누어 4등분해 주는 함수. 

각각 등분한 부불에 대해 등분된 부분이 같은 색인지 확인한 후 아니라면 다시 4등분을 해 나간다. N = 1이라면 가장 작은 단위이므로 종이색 변수(PAPER)에 추가해주고 함수를 종료한다.

isSameColor 함수는 그 부분이 전체가 같은 색을 가지는지 확인하는 함수(같은 색일 경우 더이상 진행하지 않는다.)

# 추가

정올 테스트 케이스에서는 전체가 다 같은 경우가 없어서 통과했으나 만약 전체가 같은 경우에 대한 처리(가장 처음 isSameColor(map,0,0,N) )를 해줘야 하는데 빼먹었다. 가장 처음 dnc 함수를 사용하기 전에 넣어주면 될 것 같다.