[백준] 1074번 Z(JAVA)

 

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

 

문제 이해

 2ⁿ × 2ⁿ  2차원 배열에서 Z 모양의 순서로 방문할 때 주어진 위치 (r, c)가 몇 번째로 방문되는지를 찾는 것입니다.

Z 모양 순서

배열은 4개의 부분으로 나눌 수 있습니다:

1. 왼쪽 위
2. 오른쪽 위
3. 왼쪽 아래
4. 오른쪽 아래

각 부분은 다시 동일한 방식으로 4개의 작은 부분으로 나눌 수 있습니다. 이 구조는 재귀적으로 계속됩니다.

재귀적 접근

1. 배열의 크기를 2ⁿ × 2ⁿ 에서 시작합니다.
2. 주어진 (r, c)가 배열의 어느 부분에 속하는지 파악합니다.
3. 속하는 부분에 따라 이전까지의 방문 순서에 현재 부분의 시작점을 더해줍니다.
4. 문제를 해당 부분으로 축소하여 재귀적으로 해결합니다.

배열의 크기를 4등분하여 해당 좌표가 어느 사분면에 속하는지 확인합니다.

구체적인 단계

1. 크기 확인: 현재 배열의 크기를 확인하고, 중앙을 기준으로 4개의 사분면으로 나눕니다.
2. 위치 파악: (r, c)가 어느 사분면에 있는지 확인합니다.
   • (r, c)가 1사분면(왼쪽 위)에 있다면, 더 이상의 이동 없이 현재 사분면 내부에서만 탐색합니다.
   • (r, c)가 2사분면(오른쪽 위)에 있다면, 첫 번째 사분면의 크기만큼 방문 순서를 더해주고, 2사분면 내에서 탐색을 계속합니다.
   • (r, c)가 3사분면(왼쪽 아래)에 있다면, 첫 번째와 두 번째 사분면의 크기만큼 방문 순서를 더해주고, 3사분면 내에서 탐색을 계속합니다.
   • (r, c)가 4사분면(오른쪽 아래)에 있다면, 첫 번째, 두 번째, 세 번째 사분면의 크기만큼 방문 순서를 더해주고, 4사분면 내에서 탐색을 계속합니다.
3. 반복 축소: 배열의 크기를 반으로 줄이고, 새로운 기준 좌표로 (r, c)를 변환하여 반복합니다.

 

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

public class _1074 {
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
        System.out.print(z(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                0));
    }
    private static int z(int N, int r, int c, int cnt) {
        if (N == 0) return cnt;

        int half = (int) Math.pow(2, N - 1);
        int quad;

        if (r >= half && c >= half) {
            quad = 3;
            r -= half;
            c -= half;
        } else if (r >= half) {
            quad = 2;
            r -= half;
        } else if (c >= half) {
            quad = 1;
            c -= half;
        } else {
            quad = 0;
        }
        cnt += (int) Math.pow(4, N - 1) * quad;
        return z(--N, r, c, cnt);
    }
}