[백준/C++] 1780 : 종이의 개수

  문제   

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

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

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

 

   입력   

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

 

   출력   

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

 

   예제   

 

---

   코드 및 풀이  

 

<내가 작성한 코드>

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

int n;
int num[3];
int board[5000][5000];

int dx[8] = { 1, 2, 0, 0, 1, 1, 2, 2 };
int dy[8] = { 0, 0, 1, 2, 1, 2, 1, 2 };


void paper(int k, int sx, int sy) {
    int tmp = board[sx][sy];
    if (k == 1) {
        bool same2 = true;
        for (int dir = 0; dir < 8; dir++) {
            if (tmp != board[sx + dx[dir]][sy + dy[dir]]) same2 = 0;
        }
        if (same2) num[tmp + 1]++;
        else {
            num[tmp + 1]++;
            for (int dir = 0; dir < 8; dir++) {
                num[board[sx + dx[dir]][sy + dy[dir]] + 1]++;
            }
        }
        return;
    }
    bool same1 = true;
    for (int i = sx; i < sx + k * 3; i++) {
        for (int j = sy; j < sy + k * 3; j++) {
            if (tmp != board[i][j]) same1 = 0;
        }
    }
    if (same1) num[tmp + 1]++;
    else {
        paper(k / 3, sx, sy);
        paper(k / 3, sx + k, sy);
        paper(k / 3, sx + (k * 2), sy);
        paper(k / 3, sx, sy + k);
        paper(k / 3, sx + k, sy + k);
        paper(k / 3, sx, sy + (k * 2));
        paper(k / 3, sx + k, sy + (k * 2));
        paper(k / 3, sx + (k * 2), sy + k);
        paper(k / 3, sx + (k * 2), sy + (k * 2));
    }


}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

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

    paper(n / 3, 0, 0);

    for (int i = 0; i < 3; i++) {
        cout << num[i] << "\n";
    }
}

 

이 문제는 재귀로 해결해야 한다. 왜냐하면 한 종이 안에 있는 숫자들이 전부 같지 않을 경우 9등분을 해서 다시 똑같은 과정을 반복해야 하기 때문이다.

재귀함수는 모든 원소의 숫자가 같은 지를 비교하고 같다면 해당 숫자의 개수를 추가, 같지 않다면 종이를 9등분하는 역할을 한다.

여기서 나는 재귀함수의 인자로 (한 변의 길이 / 3)과 시작점의 좌표를 받도록 설정하였다.

(종이를 9등분했을 때 한 변의 길이를 기준으로 삼고 싶어서 그렇게 했지만 그냥 한 변의 길이를 인자로 받아도 상관 없다.)

 

만약 인자로 들어온 숫자가 1이라면, 즉 한 변의 길이가 3이라면 똑같이 원소들의 숫자를 비교하고 같으면 해당 숫자의 개수를 추가하지만, 같지 않다면 9등분하지 않고 모든 원소에 해당하는 숫자의 개수를 추가해 줄 것이다.

 

-한 종이의 각 원소들의 숫자를 비교하는 방법-

한 변의 길이가 3보다 큰 종이들은 시작점의 좌표인 board[sx][sy]부터 board[sx+한 변의 길이 - 1][sy+한변의 길이 - 1]까지 돌면서 board[sx][sy]와 같지 않은 숫자가 있는 지 비교한다.

나는 board[sx][sy]를 미리 변수 tmp에 저장해 두었으며, 비교 이후에는 모든 원소의 값의 일치 여부를 bool 자료형인 same1에 저장했다.

 

한 변의 길이가 3이라면 board[sx][sy]부터 board[sx+2][sy+2]까지 돌면서 똑같이 board[sx][sy]와 비교하고 결과를 same2에 저장한다. board[sx][sy]부터 board[sx+2][sy+2]까지 도는 것을 간단하게 표현하기 위해 배열 dx, dy를 미리 설정해 두었다.

 

한 변의 길이가 1이라면 same1의 초기화된 값인 true가 그대로 유지되기 때문에 해당하는 숫자의 값의 개수만 추가해주면 된다.

 

(변의 길이에 따라 예외가 생기지 않도록 모두 확인했다!)

 

-종이를 9등분 하는 방법-

만약 한 종이에 있는 모든 원소의 값을 비교했을 때 하나라도 다른 게 있다면 종이를 9등분해야한다. 

이때 9등분한 종이들의 가장 왼쪽 상단에 있는 좌표를 시작점이라고 한다면, 그 시작점들은 다음과 같다.

(sx, sy) / (sx + k, sy) / (sx, sy+k) / (sx+k, sy+k) / (sx+2k, sy) / (sx, sy+2k) / (sx+k, sy+2k) / (sx+2k, sy+k) / (sx+2k, sy+2k) 

이때 k = (한 변의 길이 / 3)이다.

 

 

   정답 코드 분석  

// Authored by : cpprhtn
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/b8488e82105d49e89ca6f39fd8ee665b
#include <bits/stdc++.h>
using namespace std;

int N;
int paper[2200][2200];
int cnt[3]; //-1, 0, 1로 채워진 종이 갯수

//해당 종이 내부에 같은 숫자로만 채워졌는지 확인하는 함수
bool check(int x, int y, int n) {
  for (int i = x; i < x + n; i++)
  for (int j = y; j < y + n; j++)
    if (paper[x][y] != paper[i][j])
    return false;
  return true;
}
void solve(int x, int y, int z)
{
  if (check(x, y, z)) {
    cnt[paper[x][y] + 1] += 1;
    return;
  }
  int n = z / 3;
  for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
    solve(x + i * n, y + j * n, n);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    cin >> paper[i][j];
  solve(0, 0, N);
  for (int i = 0; i < 3; i++) cout << cnt[i] << "\n";
}

 

푸는 로직은 똑같지만 코드가 훨씬 간결하다.

나는 원소들을 비교하는 함수를 변의 길이가 3일 때, 3 이상일 때로 나누어져 있지만 여기선 check라는 함수로 통일시켰다.

같은 역할을 하는 코드들을 따로 함수로 분리하는 것을 습관 들여봐야겠다!

 

 

문제 출처: https://www.acmicpc.net/problem/1780

1780번: 종이의 개수