Z
문제 해석
- 2차원 배열을 Z모양으로 탐색할 때, 좌표 (r,c)를 몇번째로 방문하는 지 출력하는 문제입니다.
- 2차원 배열의 크기는 2^Nx2^N입니다.(1<=N<=15)
설계(5)
- 재귀함수를 활용하는 문제입니다.
- 모든 좌표를 탐색하면 O(2^2N)으로 시간초과가 발생합니다.
- 따라서, 분할정복알고리즘을 이용하여 특정좌표를 찾아가도록 구현하면 O(log2^N) = O(N)의 시간복잡도로 시간 내에 탐색이 가능합니다.
- 여기서 중요한 점은 정해진 좌표가 해당 재귀함수의 범위에 포함되지 않으면 return하도록 구현하는 것입니다.
- 각 왼쪽위, 오른쪽위, 왼쪽 아래, 오른쪽 아래 순으로 재귀함수를 구현합니다.
구현(30)
코드
#include <iostream>
using namespace std;
int N,r,c;
void dfs(int x, int y, int size, int sum){
if (size == 1 && x == r && y == c){
cout << sum;
return;
}
if (r< x || c < y || x + size*2<= r || y+ size*2 <= c) return;
int tmp = size/2;
dfs(x,y,tmp,sum);
dfs(x,y+tmp,tmp,sum+tmp*tmp);
dfs(x+tmp,y,tmp,sum+2*tmp*tmp);
dfs(x+tmp,y+tmp,tmp,sum+3*tmp*tmp);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> r >> c;
dfs(0,0,(1<<N),0);
return 0;
}
디버깅
- 처음에는 재귀함수의 범위를 고려하지 않고, 전부다 탐색하도록 해서 아주 느린 실행결과가 나왔습니다(840ms).
- 제가 구상하였던 시간복잡도가 되려면 범위를 체크해주었어야 했습니다.
제출결과
- 0ms
마무리
- 분할정복을 이용하는 문제였습니다. 범위체크를 통해 최적화를 하였습니다.