링크
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로만 채워진 종이의 개수를 출력한다.
예제 입력 1
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예제 출력 1
10
12
11코드 분할 설명
int N;
scanf("%d", &N);
// 2차원 배열 동적할당
paper = (int**)calloc(N, sizeof(int*));
for (int i = 0; i < N; i++)
paper[i] = (int*)calloc(N, sizeof(int));
// 종이의 각 칸의 숫자를 입력받음
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
scanf("%d", &paper[i][j]);
}- 입력되는 N의 값에 따라 배열의 크기가 유동적으로 변하므로 calloc으로 2차원 배열 동적할당을 수행하였다.
int check(int row, int col, int n) // 종이의 모든 값이 같은지 확인하는 함수
{
int c = paper[row][col]; // 종이의 첫번째 요소의 값 저장
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (c != paper[i][j]) { // 종이에 있는 값들 중 하나라도 다른게 있으면
return False; // False 반환
}
}
}
return True; // 전부 같으면 True 반환
}- 종이의 모든 값이 같은지 확인하는 check 함수이다.
- 매개변수로는 row, col, n을 전달 받는다.
- c에 종이의 첫번째 요소의 값을 저장하고 현재 종이에 있는 값들 중 하나라도 다른게 있으면 False를 반환한다.
- n은 현재 종이의 변의 길이이다.
- row와 col은 현재 종이의 첫번째 요소의 인덱스이다.
- row to row + n, col to col + n으로 한 이유는 현재 종이의 변의 길이인 n만큼만 값을 비교해야 하기 때문이다.
- 모든 값이 같으면 True를 반환한다.
void divide(int row, int col, int n) // 종이를 자르는 함수
{
if (check(row, col, n)) { // 종이의 모든 값이 같으면
type[paper[row][col] + 1]++; // -1인 경우에는 type[0]++, 0인경우에는 type[1]++, 1인경우에는 type[2]++
return; // 분할 x
}
// 종이의 값들 중 다른 것이 있다면 분할 수행
int num = n / 3; // NxN 크기 이므로 9등분 하기 위해서는 N을 3으로 나누면 됨
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
divide(row + i * num, col + j * num, num); // 9등분된 각 종이들의 첫 요소의 좌표를 기입
}
}
}- 종이를 자르는 divide 함수이다.
- 매개변수로는 row, col, n을 전달받는다.
- 현재 종이의 모든 값이 같은지 check함수를 통해 확인하고 종이의 모든 값이 같으면 종이에 적혀있는 값으로 채워진 종이의 개수를 카운팅하고 함수를 종료한다. 종이가 1x1까지 잘리진 경우에는 항상 종이의 모든 값이 같아지므로 재귀 호출의 종료조건이 된다.
- 종이의 값들 중 다른 것이 있다면 종이를 9등분한다.
- 종이는 NxN 크기 이므로 9등분을 하기 위해서는 변의 길이를 3으로 나누면 된다.
- 이후 나눠진 9개의 종이들 각각 divide 함수를 적용한다. 이때 9등분된 각 종이들의 첫 요소의 좌표를 매개변수로 전달한다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#define True 1
#define False 0
int** paper; // 종이의 각 칸의 숫자를 입력받을 2차원 배열
int type[3] = { 0, 0, 0 }; // -1, 0, 1의 개수를 카운팅 할 1차원 배열
int check(int row, int col, int n) // 종이의 모든 값이 같은지 확인하는 함수
{
int c = paper[row][col]; // 종이의 첫번째 요소의 값 저장
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (c != paper[i][j]) { // 종이에 있는 값들 중 하나라도 다른게 있으면
return False; // False 반환
}
}
}
return True; // 전부 같으면 True 반환
}
void divide(int row, int col, int n) // 종이를 자르는 함수
{
if (check(row, col, n)) { // 종이의 모든 값이 같으면
type[paper[row][col] + 1]++; // -1인 경우에는 type[0]++, 0인경우에는 type[1]++, 1인경우에는 type[2]++
return; // 분할 x
}
// 종이의 값들 중 다른 것이 있다면 분할 수행
int num = n / 3; // NxN 크기 이므로 9등분 하기 위해서는 N을 3으로 나누면 됨
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
divide(row + i * num, col + j * num, num); // 9등분된 각 종이들의 첫 요소의 좌표를 기입
}
}
}
int main()
{
int N;
scanf("%d", &N);
// 2차원 배열 동적할당
paper = (int**)calloc(N, sizeof(int*));
for (int i = 0; i < N; i++)
paper[i] = (int*)calloc(N, sizeof(int));
// 종이의 각 칸의 숫자를 입력받음
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
scanf("%d", &paper[i][j]);
}
// 분할 수행
divide(0, 0, N);
for (int i = 0; i < 3; i++)
printf("%d\n", type[i]);
// 메모리 해제
for (int i = 0; i < N; i++)
free(paper[i]);
free(paper);
return 0;
}제출 결과
IT Velog