[BOJ] 1074 Z

1074 Z

난이도 : 실버 1
유형 : 재귀, 분할정복

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

문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

풀이

분할정복과 재귀를 이용하여 풀 수 있는 문제.
아직 분할정복과 재귀에 익숙하지 않아 해맸던 문제이다.
일단 4등분해서 Z모양으로 방문하기 때문에 분기를 4번하고, 재귀를 호출하며 원하는 R,C값을 찾아주면된다.

코드

import java.util.Scanner;

/**
 * BOJ_1074_S1_Z
 * @author mingggkeee
 * 재귀, 분할정복
 */

public class BOJ_1074 {
	
	static int n, R, C;
	static int N;
	static int count;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();	// 2의 N승 * 2의N승
		
		N = (int)Math.pow(2, n);	// 한변의 사이즈
		
		R = sc.nextInt();	// 행
		C = sc.nextInt();	// 열
		
		search(N, R, C);
		
		System.out.println(count);
		
		
		sc.close();
	}
	
	public static void search(int N, int R, int C) {
		if(N==1) {
			return;
		}
		
		if(R < N/2 && C < N/2) {
			search(N/2, R, C);
		}
		else if(R < N/2 && C >= N/2) {
			count += N * N / 4;
			search(N/2, R, C - N/2);
		}
		else if(R >= N/2 && C < N/2) {
			count += (N * N / 4) * 2;
			search(N/2, R - N/2, C);
		}
		else {
			count += (N * N / 4) * 3;
			search(N/2, R - N/2, C - N/2);
		}
	}

	
}