04.06. Z[Divide and conquer][백준 1074]

https://www.acmicpc.net/problem/1074

1074번: Z

 

 

Algorithm classification : Divide and conquer, Recursion

 

04.06.1. Problem

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

04.06.2. Input limit

첫째 줄에 정수 N, r, c가 주어진다.

 

04.06.3. Output

r행 c열을 몇 번째로 방문했는지 출력한다.

 

04.06.4. Solution

앞서 소개한 쿼드 트리 문제와 동일합니다. 차이점은 하나의 문제만 계속 파고들면 된다는 것이죠. 따라서 정복단계가 단순합니다.

void cal(int c_x, int c_y, int size){
	if(c_x == c+1 && c_y == r+1){
		printf("%d\n", result);
		return;
	}
	if(c_x <= c+1 && c+1 < c_x + size && c_y <= r+1 && r+1 < c_y + size){
		cal(c_x, c_y, size/2);
		cal(c_x+size/2, c_y, size/2);
		cal(c_x, c_y+size/2, size/2);
		cal(c_x+size/2, c_y+size/2, size/2);
	}
	else{
		result += size*size;
	}
}

 

	cal(1, 1, pow(2, n));