[BOJ 1074] Z

- 문제 요약

 

크기가 2^N x 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다.

아래의 사진은 2^2 x 2^2 크기의 배열을 방문한 순서이다.

Z모양 탐색 예시

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. (1 ≤ N ≤ 15 / 0 ≤ r, c < 2^N)

 

 

- 알고리즘 정리

 

분할정복을 이용하여 해결했습니다. 2^N 크기의 배열을 십자 모양으로 4등분 해서, 각 블록마다 재귀를 돌려줍니다.

r과 c가 현재 블럭블록 안에 있다면 그 상태로 재귀를 돌리고, 만약 현재 블록 안에 없다면 현재 블록의 크기만큼 탐색을 마치고 다음 블록으로 넘어간다는 소리가 됩니다. 그러므로 현재 블록의 넓이를 결괏값에 더해주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,r,c,result;

void f(int x,int y,int w){
	if(c==x && r==y){
		cout<<result;
		return;
	}
	if(c<x+w && r<y+w && c>=x && r>=y){
		f(x,y,w/2);
		f(x+w/2,y,w/2);
		f(x,y+w/2,w/2);
		f(x+w/2,y+w/2,w/2);	
	}
	else{
		result+=pow(w,2);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>r>>c;
	f(0,0,pow(2,n));
}

코드 제출 결과