[백준] 1780번 종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

이 문제는 쿼드트리랑 비슷하다.

다른 점은 쿼드트리는 4등분이지만 이건 9등분이다.

 

이 문제도 똑같다.

0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

이런거에서 9개씩 잘라야 한다.

왜냐하면 문제에서 9개씩 잘라야 한다고 나왔있기 때문!

 

또, 입력줄을 살펴보면 3^k꼴이라고 한다. 즉, 무조건 3으로 나눠진다는 뜻이다.

그러면 어떻게 9개씩 자를수 있을까?

지금 보는 형태는 이차 배열 형태다.

그렇기 때문에 x쪽으로 3개 y쪽으로 3개 이렇게 나누면 된다.

그러면

0 0 0 
0 0 0 
0 0 0 

1 1 1
1 1 1 
1 1 1 
 
-1 -1 -1
-1 -1 -1
-1 -1 -1

1 1 1 
1 1 1 
1 1 1 

0 0 0
0 0 0
0 0 0

0 0 0
0 0 0
0 0 0


0 1 -1   0 1 -1   0 1 -1
0 -1 1   0 1 -1   0 1 -1
0 1 -1   1 0 -1   0 1 -1

이렇게 나눠지는데.. 

문제를 읽어보면

종이가 같은 수로 되어있다면 그 종이는 한개로 사용된다.

이는 맨위 같은 경우 0 : 1개라고 할수 있다!

 

 

그러면 어떻게 알 수 있을까?

같은게 없으면 된다.(그건 안다고)

0,0부터 맨 밑까지 다른 수라면 false를 

같은 수라면 true를...

 

처음에는 쿼드트리문제랑 했던거랑 비슷하게 변수로 할당해서 했다. 하지만 그러니 틀렸습니다가 나왔다.

(딱히 중요한 말이 아니니까 ㅎㅎ)

 

그러면 이런 코드가 생긴다.

#include <bits/stdc++.h>
using namespace std;

int arr[6561][6561];

int mone;
int one;
int zero;


bool issame(int n, int x, int y) {

  for(int i = x;i<x+n;i++) {
    for(int j = y;j<y+n;j++) {
      if(arr[i][j] != arr[x][y]) {
        return false;
      }
    }
  }
  return true;
}
void split(int n,int x, int y) {
  if (issame(n,x,y)) {
    if (arr[x][y] == 0) {
      zero++;
    } else if (arr[x][y] == -1) {
      mone++;
    } else if (arr[x][y] == 1) {
      one++;
    }
    return;
  } else {
    split(n/3,x,y);
  
    split(n/3,n/3+x,y);
  
    split(n/3,2*n/3+x,y);

    split(n/3,x,n/3+y);          
  
    split(n/3,n/3+x,n/3+y);          
  
    split(n/3,2*n/3+x,n/3+y);
  
    split(n/3,x,2*n/3+y);       
  
    split(n/3,n/3+x,2*n/3+y);     
  
    split(n/3,2*n/3+x,2*n/3+y);

    }

}
int main(void) {     
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int n;
  cin >> n;

  for(int i = 0; i<n;i++) {
    for(int j = 0;j<n;j++) {
      cin >> arr[i][j];
    }
  }

  split(n,0,0);

  cout << mone << "\n";
  cout << zero << "\n";
  cout << one << "\n";

}

 

쿼드 트리 문제부터 생각하고 있었지만 분할정복은

제귀를 한개가 아닌 여러개 이용하는 방법이라 생각한다.

다른 코드를 보면 1개만 되어있는 코드가 있을텐데 자세히 보면 반복문으로 되어있다.

 

아래 split(...)을 설명하자면..

 

x좌표와y좌표에 0부터 n까지를 작성해보자. 

그러면

첫번째는 0~2 / 0~2로

두번째는 3~5 / 0~2로

세번째는 6~8 / 0~2로

네번쨰는 0~2/ 3~5로 쪼개진다.

 

그러면 n/3인 이유는 그냥 9등분(즉, x좌표3등분,y좌표3ㄷ등분)이기때문이다.

 

그래서 0~2를 하려면 원래시작도

0부터 n까지시작이기 때문에 굳이 변경할 필요는 없다.

 

다른건 다르다.

3~5같은 경우는

 

원래크기 (예제에서)  9이기때문에

9가 3이 되려면 6을 빼던가 3을 나눠주면 된다.

하지만 6을 빼주는건 답이아니기 때문에  pass.. (물론 이게 답일 수도... 난 안해봤지만..ㅎㅎ)

3을 나눠준다는건 n/3 이라는 말과 똑같다. 하지만 이것만 작성하면 틀리기 된다,

만약 한번더 나눠야한다고 생각해보자.ㅎㅎ

그래서 x를 더한거다. 그래야 다다음도 계산할 수 있기 때문이다.

 

마지막으로 6~8을 알아보자.

뭐 크기는 작아졌기 때문에 n/3이 맞지만

6은 어떻게 만들까? 바로 3에서 2를 곱해주면된다.

그러면 n/3 * 2 가 된다. 이렇게 하면된다.물론 여기에도 x또는 y를 더해줘야하는건 변함없는사실이지만...ㅎㅎ

 

저 코드를 더 간단하게 하고 싶다면

반복문을 이용해서 정리해도 좋고,

one, zero이 부분을 배열로 묶어서 보관해도 좋다.

 

핵심은 재귀를 여러번 사용하게 되면 분할 정복이다.!

 

#include <iostream>
#define MAX_SIZE 2187

int input();
void cutPaper(int i, int j, int n);
int paper[MAX_SIZE][MAX_SIZE];
int count[3] = {0, };

int main() {
    int N = input();
    cutPaper(0, 0, N);
    for(auto c : count)
        printf("%d\n", c);
    return 0;
}

int input() {
    int N;
    scanf(" %d", &N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf(" %d", &(paper[i][j]));
        }
    }
    return N;
}

void cutPaper(int i, int j, int n) {
    int iTill = i + n;
    int jTill = j + n;
    int init = paper[i][j];
    bool flag = false;
    for (int k = i; k < iTill && !flag; k++) {
        for (int l = j; l < jTill; l++) {
            if (init != paper[k][l]) {
                flag = true;
                break;
            }
        }
    }
    n /= 3;
    if (flag) {
        for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
                cutPaper(i + k * n, j + l * n, n);
            }
        }
    }
    else {
        count[init+1]++;
    }
}