1074 Z

Z

문제

한수는 크기가 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

풀이

이 문제는 큰 문제를 작은 문제로 나눠서 해결하는 분할 정복 문제이다.
우선 n을 기준으로 4사분면으로 나누어 지는 것을 확인할 수 있다.
n이 0보다 클 때 r과 c가 속한 사분면을 찾은 후 r과 c를 상대위치로 재조정한다.
ex) (r,c) => 4사분면일경우 r - 2^n, c - 2^n
그리고 답에 지나온 사분면의 칸 갯수만큼 더해준다.
이를 n이 0이 될때까지 반복하면 된다.

코드

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();  

        System.out.println(func(n, r, c, 0));  

    }  

    static int func(int n, int r, int c, int ans) {  
        if (n == 0) {  

            return ans;  
        }  


        int quadrant = find(n, r, c);  
        int temp = (int) Math.pow(2, n - 1);  
        int quadrantSize = temp \* temp;  

//        System.out.println(n + " " + r + " " + c + " " + ans + " " + quadrant);  

        switch (quadrant) {  
            case 1:  
                return func(n - 1, r, c, ans);  
//                break;  
            case 2:  
                return func(n - 1, r, c - temp, ans +quadrantSize);  
//                break;  
            case 3:  
                return func(n - 1, r - temp, c, ans + (2 \* quadrantSize));  
//                break;  
            case 4:  
                return func(n - 1, r - temp, c - temp, ans + (3 \* quadrantSize));  
//                break;  
            default:  
                return -1;  
        }  

    }  

    static int find(int n, int r, int c) {  
        int xLen = (int)Math.pow(2, n - 1);  
        int yLen = xLen;  

        if(r < xLen && c < yLen){  
            return 1;  
        } else if (r >= xLen && c < yLen) {  
            return 3;  
        } else if (r < xLen && c >= yLen) {  
            return 2;  
        } else{  
            return 4;  
        }  
    }  
}