백준 - 1074번(Z)

문제 출처: https://www.acmicpc.net/problem/1074

문제

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

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

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

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

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

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

public class Main {

    private static int answer = 0;
    private static int[][] arr = {
            { 0, 1 },
            { 2, 3 },
    };

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int r = Integer.parseInt(tokenizer.nextToken());
        int c = Integer.parseInt(tokenizer.nextToken());

        recursiveCall(N, r, c);

        System.out.println(answer);
    }

    private static void recursiveCall(int N, int i, int j) {
        if (N == 1) {
            answer += arr[i][j];
            return;
        }

        int center = 1 << (N - 1);
        int right = 1 << ((N - 1) * 2);
        int bottom = 1 << ((N - 1) * 2 + 1);

        // 좌표의 위치 찾기
        if (i < center && j >= center) {
            // 1사분면
            j -= center;
            answer += right;
        } else if (i < center && j < center) {
            // 2사분면

        } else if (i >= center && j < center) {
            // 3 사분면
            i -= center;
            answer += bottom;
        } else {
            // 4 사분면
            i -= center;
            j -= center;
            answer += right + bottom;
        }

        recursiveCall(N - 1, i, j);
    }

}

• 규칙성이 한번에 눈에 들어오지 않아 시간이 꽤 소요된 문제이다.
• 주요 로직은, 전체를 4등분하여 사분면에 따라 적절한 연산을 수행한다.
• 1사분면은 열이 줄어들고, 3사분면은 행이 줄어들고, 4사분면은 행과 열 모두 줄어든다. 현재 상태에서의 중간값(2^N-1)) 만큼 줄어든다.
• N이 1이 될 때까지 재귀를 반복한다. N이 1이라는 것은, 2*2 배열이 된 것으로 제일 기본값인 0, 1, 2, 3이 들어가있다.
• N이 1이 될 때까지의 값들을 더하고, 최종 위치에 따라 값을 더하여 결과를 도출한다.