[BOJ] 백준 1780번 종이의 개수

KwangYong·2021년 11월 17일

boj 재귀

BOJ

목록 보기

38/69

링크

https://www.acmicpc.net/problem/1780

문제

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

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

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

입력

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

출력

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

풀이

 #include <iostream>

using namespace std;
int n, cnt[3];
int board[2187][2187];

void solve(int n , int row, int col ) {
	bool isFail = false;
	int success = -2; 
	for (int i = row; i < row + n; i++)
		for (int j = col; j < col + n; j++) {
			if (board[i][j] != board[row][col]) {
				isFail = true;
				break;
			}
			else
				success = board[0][0];
		}
	if (isFail == true) {
		int divThird = n / 3; //divThird가 인자로 들어가야겠다.
		for (int k = 0; k < 3; k++) { //총 9번만큼 불러야됨. 9등분
			for (int l = 0; l < 3; l++) {
				solve(divThird, row + divThird * k , col + divThird * l);
			}
		}
	}
	else {
		cnt[board[row][col] + 1] += 1;
		return;
	}
}

int main() {
	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];
		}
	solve(n, 0, 0);
	for (int i = 0; i < 3; i++)
		cout << cnt[i] << '\n';
}

👉🏻 바킹독 문제 정답 풀이

// 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";
}