한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
첫째 줄에 정수 N, r, c가 주어진다.
r행 c열을 몇 번째로 방문했는지 출력한다.
#include <iostream>
using namespace std;
int row, col, cnt = -1;
int z(int l, int r, int c){
if(l == 2){
if(row > r || col > c){
cnt += 4;
return -1;
}
for(int i = 1; i >= 0; i--){
for(int j = 1; j >= 0; j--){
cnt++;
if((r - i == row) && (c - j == col)) return cnt;
}
}
return -1;
}
else{
int ans, tr, tc;
for(int i = 1; i >= 0; i--){
for(int j = 1; j >= 0; j--){
tr = r - ((l / 2) * i);
tc = c - ((l / 2) * j);
if(row > tr || col > tc) cnt += (l / 2) * (l / 2);
else{
ans = z(l / 2, tr, tc);
if(ans != -1) return ans;
}
}
}
return -1;
}
}
int main(){
int N, n = 1;
cin >> N >> row >> col;
for(int i = 0; i < N; i++) n *= 2;
cout << z(n, n - 1, n - 1);
}
찾으려는 좌표가 어느 사분면에 있는지 확인할 수 있기 때문에 조건을 주어 시간을 줄일 수 있다