모든 칸을 확인했을 때, 결과는 2가지다.
칸의 색깔 비교는 첫 칸을 기준으로 한다.
(0,0) 부터 (3,3)까지 4x4 만큼의 사각형을 확인한다고 가정한다. 한 변의 길이는 4 다.
1) 모든 칸을 확인했을 때 모두 같은색임 -> 첫 칸 색깔에 카운팅++ 하고 끝낸다.
2) 모든 칸을 확인하는데 첫 칸과 다른 색 발견 -> 4의 반토막인 길이 2의 사각형 4개를 탐색한다.
4개로 쪼개지니까 재귀함수를 4번 돌려야한다.
(0, 0) 부터 2길이만큼 탐색한다.
(0, 1)부터 2길이만큼 탐색한다.
(1, 0)부터 2길이만큼 탐색한다.
(1,1)부터 2길이만큼 탐색한다.
#include <bits/stdc++.h>
using namespace std;
int N, white_cnt, blue_cnt; // 하양 0, 파랑 1 로 표시
int arr[129][129];
void check(int x, int y, int len){ // 행, 열, 한 변 길이
int color = arr[x][y];
for(int i = x; i < x+len; i++){ // 행
for(int j = y; j < y+len; j++){ // 열
if(color != arr[i][j]){
check(x, y, len/2);
check(x, y + len/2, len/2);
check(x + len/2, y, len/2);
check(x + len/2, y + len/2, len/2);
return;
}
}
}
if(color == 1) blue_cnt++; // 전부 1이었다면 파랑 카운팅
else white_cnt++;
}
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 >> arr[i][j];
check(0, 0, N);
cout << white_cnt << '\n' << blue_cnt;
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 네 번째 점 백준 3009번 c++ (0) | 2022.02.21 |
|---|---|
| 백설 공주와 일곱 난쟁이 백준 3040번 c++ (0) | 2022.02.20 |
| 최소 힙 백준 1927번 c++ (0) | 2022.02.19 |
| ATM 백준 11399번 c++ (0) | 2022.02.19 |
| 나는야 포켓몬 마스터 이다솜 백준 1620번 c++ (0) | 2022.02.19 |