[JAVA] 백준 (실버1) 1074번 Z

링크

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

---

문제 설명

정답률 41.028%
한수는 크기가 $2^N × 2^N$인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 $2^{N-1} × 2^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 $2^2 × 2^2$ 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

---

입력 예제

2 3 1

---

출력 예제

11

---

정답 코드

1 | 2
ㅡㅡ
3 | 4
2차원 배열을 좌표평면으로 생각할 때 위와 같이 4등분한다. 편의상 문제의 순서대로 사분면으로 호칭한다.

우선 인자로 입력받은 좌표의 사분면을 구한다. 몇 사분면인지 구한 뒤 인덱스를 구하는데

이 그림으로 생각해보면 각 사분면의 첫번째 인덱스는 변의 길이의 제곱을 나눈 뒤 4로 나누어 각각 0~3을 곱한게 된다. 그리고 1사분면을 기준으로 좌표를 갱신하여 재귀 함수를 호출한다. 이때 변의 길이는 나누기 2를 하여 넘기고 인덱스는 누적하여 계산한다. 변의 길이가 1이 되면 재귀 호출을 중단한다.

코드

public class Main {

    static int index;

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

        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int r = sc.nextInt();
        int c = sc.nextInt();
        int length = (int) Math.pow(2, N);

        calculateIndex(length, r, c);
        System.out.println(index);
    }

    private static void calculateIndex(int length, int r, int c) {
		//length가 1일 경우 재귀 중단
        if (length == 1) {
            return;
        }

        int half = length / 2;
        int temp = (int) Math.pow(length, 2) / 4;

        //1사분면
        if (r < half && c < half) {
            index += temp * 0;
            calculateIndex(half, r, c);
        } 
        //2사분면
        else if (r < half && c >= half) {
            index += temp * 1;
            calculateIndex(half, r, c - half);
        } 
        //3사분면
        else if (r >= half && c < half) {
            index += temp * 2;
            calculateIndex(half, r - half, c);
        } 
        //4사분면
        else {
            index += temp * 3;
            calculateIndex(half, r - half, c - half);
        }
    }

}