[백준] 1074번 Z

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

1074번: Z

문제

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

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

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

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

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

풀이

이 문제는 딱 봐도 재귀적인 문제고, 분할정복 문제이다. 2차원 배열을 좌표평면처럼 생각하면, 각각이 몇 사분면에 속하는지에 따라 탐색순서가 결정됨을 알 수 있다.

N = 1인 경우를 보면

1사분면일 때 0, 2사분면일때 1, 3사분면일때 2, 4사분면일때 3임을 알 수 있다. 

N = 2인 경우를 보면

각 사분면에 해당되는 칸이 4개씩 존재한다. 또한, 그 4개의 칸을 좌표평면으로 보고 4개의 칸이 또 몇 사분면에 위치하는지에 따라 순서가 결정된다.

예컨데 1행 1열은 순서대로 1사분면, 4사분면이라 (1-1)*4 + (4-1) = 3이 되고, 3행 2열의 경우 4사분면, 3사분면이라 (4-1) * 4 + (3-1) = 14가 된다. 즉, r 행 c열이 순서대로 몇사분면에 해당되는지 적어둔 수열을 A라 하면 다음 수식이 성립한다.

즉, 주어진 n, r, c 을 사분면정보가 담긴 배열로 변환하면, O(n) 안에 문제를 풀 수 있다. 이때 N이 최대 15이므로, 사실상 상수시간에 문제를 풀 수 있게 된다.

여기까지 하고 남은건 사분면정보를구하는 일뿐인데 사분면정보를 구하는것이 생각보다 좀 까다로웠다. 우선, 좌표평면으로 볼 영역의 양 끝 지점을 알아야 한다. n, r, c rk 3, 5, 3 으로 입력된 경우를 예로들면

이 그림에서 노란색 원은 첫번째 사분면 정보를 구할때 사용되는 좌 우측 끝을 표시한 것이고, 노란색 사각형은 이때의 사분면 판단기준이 되는 기준점을 표시한 것이다. 초록색 원은 두번째 사분면 정보를 구할 때 사용되는 좌 우측끝을 표시한 것이고 초록색 사각형은 이때의 기준점을 표시한 것이다. 파란색 원은 r행 c열 을 표시한 것이다. 

사분면 정보가 무었인지에 따라, 다음번 사분면정보를 구할때 사용되는 기준점을 정하는 방법이 달라진다. 위 예시에서 첫번째 사분면 정보가 2 사분면 일 때, 죄측 끝의 열은 이전 사분면기준점의 열과 같고, 행은 이전 사분면기준점의 행 - (이전 사분면의 각 사분면의 행길이)가 된다. 우측끝은  좌측끝이 결정되었고, 길이가 정해지니 자동으로 구해진다. 

이와같이 이전의 사분면정보가 무었인지에 따라 다음 사분면기준점을 정하는 방법 4가지를 모두 구했고, 이를 코드로 옮겨 보면 아래와 같다.

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();
		int c = sc.nextInt();
		int[] positions = new int[n];
		int nback = n;
		positions= getPosition(n, r, c);

		int ret = 0;
		for(int i=0;i<nback;i++) {
			ret = ret + (int)Math.pow(4, nback-i-1) * (positions[i]-1);
		}
		System.out.println(ret);
		
	}
	public static int[] getPosition(int n, int r, int c) {
		int[] position = new int[n];
		int leftR=0,leftC=0;
		int rightR=(int)Math.pow(2,n)-1,rightC=rightR;
		int piviotR = (leftR+rightR)/2 + 1;
		int piviotC = (leftC+rightC)/2 + 1;
		for(int i=n;i>=1;i--) {
			if(r<piviotR && c<piviotC) {
				position[n-i]=1;
				rightR = piviotR-1;
				rightC = piviotC-1;
			}else if(r<piviotR && c>=piviotC) {
				position[n-i]=2;
				leftC = piviotC;
				leftR = piviotR - (int)Math.pow(2, i-1);
				rightR = leftR + (int)Math.pow(2, i-1)-1;
				rightC = leftC + (int)Math.pow(2, i-1)-1;
			}else if(r>=piviotR && c<piviotC) {
				position[n-i]=3;
				leftR = piviotR;
				leftC = piviotC - (int)Math.pow(2, i-1);
				rightR = leftR + (int)Math.pow(2, i-1)-1;
				rightC = leftC + (int)Math.pow(2, i-1)-1;
			}else {
				position[n-i]=4;
				leftR = piviotR;
				leftC = piviotC;
			}
			piviotR = (leftR+rightR)/2 + 1;
			piviotC = (leftC+rightC)/2 + 1;
		}
		return position;
	}
}