문제
풀이
분할 정복을 사용하여 풀 수 있는 문제입니다.
재귀 함수를 사용하여 현재 검사하는 정사각형의 모든 수가 같지 않다면 사각형을 4등분으로 나눠서 재귀함수를 호출해줍니다.
만약 현재 검사하는 정사각형의 모든 수가 같다면 0 또는 1의 개수를 1 증가시킨 후 재귀함수를 호출하지 않고 바로 return 해줍니다.
저는 처음에 재귀함수의 인자를 다음과 같이 설정해줬는데, 시간초과가 일어났습니다.
1
2
3
void zip(int y,int x,int size,vector<vector<int>> arr){
// ....
}
위의 코드가 왜 시간초과가 날까요?
바로 arr 벡터를 참조형으로 받지 않아서입니다. 따라서 매번 재귀함수 호출 때 마다 일일이 arr 벡터를 복사하게 돼서 시간초과가 일어나게 됩니다.
그래서 다음과 같이 arr을 참조형으로 바꿔주니 시간초과가 일어나지 않았습니다.
1
2
3
void zip(int y,int x,int size,vector<vector<int>> &arr){
// ....
}
다음은 전체 소스 코드입니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <string>
#include <vector>
using namespace std;
int zero,one; // 0의 개수, 1의 개수
void zip(int y,int x,int size,vector<vector<int>> &arr){
int cur = arr[y][x]; // 기준값
bool flag=true; // 현재 사각형이 모두 같은수라면 true
for(int i = y ; i < y + size ; i++){
if(!flag) break;
for(int j = x ; j < x+size ; j++){
if(cur != arr[i][j]){
flag = false;
break;
}
}
}
// 모두 같은 수라면 0 또는 1 의 개수 증가 후
// 재귀 호출 하지 않고 바로 return
if(flag){
cur==0 ? zero++ : one++ ;
return;
}
// 현재 사각형을 4등분하여 재귀함수 호출
zip(y,x,size/2,arr);
zip(y,x+size/2,size/2,arr);
zip(y+size/2,x,size/2,arr);
zip(y+size/2,x+size/2,size/2,arr);
}
vector<int> solution(vector<vector<int>> arr) {
vector<int> answer;
zip(0,0,arr.size(),arr);
answer.assign({zero,one});
return answer;
}
