반응형
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
💡 분할과 정복 ** 쿼드트리 문제와 유사
[문제]
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
[입력]
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
[출력]
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
✅ 문제 풀이
- 분할과 정복을 통해 해결할 수 있는 문제이다.
- 문제는 처음 size에서 3등분 해가며 분할한다.
- 입력으로 주어진 size에서 시작하여, size 만큼 배열을 순회한다.
- 순회하다가 첫 값과 달라지는 부분이 발생하면, 9등분으로 나뉘어야 하기 때문에, size를 3등분 한다.
- 그리고 해당 함수를 각 9등분의 첫 값의 좌표에 맞추어 9번의 재귀호출을 한다.
- 첫번째 조각의 첫 좌표는 이전의 첫 좌표와 항상 동일하고, 두번째 조각의 첫 좌표는 y를 size만큼 더한 값이고, 세번째 조각의 첫좌표는 y를 size*2만큼 더한 값이다.
- 네번째 조각의 첫좌표는 x를 size 만큼 더한 값이고, 다섯번째 조각의 첫좌표는 x와 y 모두 size 만큼 더한 값이다...
- 이렇게 9등분을 차례차례 좌표를 부여하고 재귀호출 하면된다.
- 재귀호출 뒤에는 동작이 없기 때문에 바로 return하도록 하고, 만약 해당 size에서 모든 값이 동일했다면, 해당 값을 1 count하도록 한다.
- 이때 카운트는 map을 통해서 -1, 0,1을 key로 하였고, 0으로 자동 초기화 되는 값에 증가 연산자로써 연산되도록 구현하였다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int n;
vector<vector<int>> arr;
map<int, int> m;
void func(int size, int x, int y) {
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (arr[x][y] != arr[i][j]) {
int new_size = size / 3;
func(new_size, x, y);
func(new_size, x, y + new_size);
func(new_size, x, y + new_size * 2);
func(new_size, x + new_size, y);
func(new_size, x + new_size, y + new_size);
func(new_size, x + new_size, y + new_size * 2);
func(new_size, x + new_size * 2, y);
func(new_size, x + new_size * 2, y + new_size);
func(new_size, x + new_size * 2, y + new_size * 2);
return;
}
}
}
m[arr[x][y]]++; //해당 키가 map에 없으면, 자동으로 키 생성 및 0으로 초기화하고 증가시킴.
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
arr.resize(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
func(n, 0, 0);
cout << m[-1] << "\n" << m[0] << "\n" << m[1];
return 0;
}반응형
'CO-TE > 백준' 카테고리의 다른 글
| [백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색 (1) | 2024.01.22 |
|---|---|
| [백준] 12865번 C++ "평범한 배낭" 풀이 / DP, 동적계획법 (0) | 2024.01.12 |
| [백준] 1149번 C++ "RGB거리" 풀이 / DP, 동적 계획법 (1) | 2024.01.09 |
| [백준] 1764번 C++ "듣보잡" 풀이/ 문자열 처리 (0) | 2023.12.28 |
| [백준] 11660번 C++ "구간 합 구하기 5" 풀이 / 누적합, 2차원 벡터 (1) | 2023.12.22 |
