백준 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일 때의 예이다.

입력

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

출력

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

코드

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

public class Main{
    static int r;
    static int c;
       static int answer2;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        StringTokenizer st=null;
        st=new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        r=Integer.parseInt(st.nextToken());
        c=Integer.parseInt(st.nextToken());

        //한 변의 길이는 2^N
        //만약 N이 2라면 한변의 길이는 4
        int length=(int)(Math.pow(2,N));
         recursive(0,0,length,0);
        System.out.println(answer2);

    }
    //length는 한 변의 길이....
    private static void recursive(int x, int y, int length,int number) {
        if(x==r&&y==c){
            answer2=number;
            return;
            //정답 찾음
        }
        if(!(x<=r&&r<=x+length&&y<=c&&c<=y+length)){
            return;
        }
        if(length<1){
            return;
        }
        length=length/2;
        recursive(x,y,length,number);
        recursive(x,y+length,length,number+length*length);
        recursive(x+length,y,length,number+length*length*2);
        recursive(x+length,y+length,length,number+length*length*3);

    }

}