[BOJ/Java] 백준 1074번 - Z

백준 #1074 Z

 

1074번: Z

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int N, r, c, cnt;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		int size = (int) Math.pow(2, N);
		calc(0, 0, size);
	}
	
	public static void calc(int x, int y, int size) {
		if (size == 2) {
			calcZ(x, y, size);
			return;
		}
		
		size /= 2;
		if (r < x+size && c < y+size) {
			calc(x, y, size);  // 제1사분면			
		} else if (r < x+size && c >= y+size) {
			cnt += size * size;
			calc(x, y+size, size);  // 제2사분면			
		} else if (r >= x+size && c < y+size) {
			cnt += (size * size) * 2;
			calc(x+size, y, size);  // 제3사분면			
		} else {
			cnt += (size * size) * 3;
			calc(x+size, y+size, size);  // 제4사분면			
		}
		
	}
	
	public static void calcZ(int x, int y, int size) {
		int[] dx = {0, 0, 1, 1};
		int[] dy = {0, 1, 0, 1};
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx == r && ny == c) {
				System.out.println(cnt);
				System.exit(0);
			} else {
				cnt++;
			}
		}
		
	}

}

재귀와 분할과 정복 이용! 재귀만 이용하면 시간 초과가 난다.

이진 탐색 기법을 이용해서 현재 탐색하려는 행과 열이 찾으려는 행과 열보다 작으면 제 1사분면을 탐색하여 들어가고, 행은 작고 열은 크다면 제 2사분면을, 행은 크고 열은 작다면 제 3사분면을, 둘 다 크다면 제 4사분면을 탐색한다. 이때 들어가려려는 사분면 이전 사분면까지 방문한 것으로 치고 방문 순서를 계산해주어야 한다. 탐색 크기가 2*2가 되면 한 칸씩 Z 모양으로 방문하며 찾으려는 행과 열의 위치를 찾고, 찾으면 그때까지 계산한 방문 순서를 출력해준다.