JAVA 백준 1074 Z (재귀)

 

 

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

 

---

문제

1. 첫째 줄에 정수 N (1 <= N <= 15) , r, c (0 <= r, c <= 2^N) 가 주어진다.
2. 크기가 [ 2^N ][ 2^N ]인 2차원 배열을 Z모양으로 탐색한다. 이 때 N이 2 이상일 경우 [ 2^N-1 ][ 2^N-1 ] 크기로 배열을 4등분하여 재귀적으로 Z모양 탐색을 진행한다.
3. 정수 세 개가 주어졌을때 r행 c열을 몇 번째로 방문하는지 출력한다.

---

 

 

최종 코드

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

public class Main {
    public static int num = 0;

    public static void repeatZ(int N, int r, int c) {
        boolean rFlag = false;
        boolean cFlag = false;

        if (r < (int) Math.pow(2, (N - 1))) {
            rFlag = true;
        }
        if (c < (int) Math.pow(2, (N - 1))) {
            cFlag = true;
        }

        if (N == 0) {
            return;
        }

        if (rFlag && cFlag) {
            num += 0 * (int) Math.pow((int) Math.pow(2, (N - 1)), 2);
            repeatZ(N - 1, r, c);
        } else if (rFlag) {
            num += 1 * (int) Math.pow((int) Math.pow(2, (N - 1)), 2);
            repeatZ(N - 1, r, c - (int) Math.pow(2, (N - 1)));
        } else if (cFlag) {
            num += 2 * (int) Math.pow((int) Math.pow(2, (N - 1)), 2);
            repeatZ(N - 1, r - (int) Math.pow(2, (N - 1)), c);
        } else {
            num += 3 * (int) Math.pow((int) Math.pow(2, (N - 1)), 2);
            repeatZ(N - 1, r - (int) Math.pow(2, (N - 1)), c - (int) Math.pow(2, (N - 1)));
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        repeatZ(N, r, c);

        System.out.println(num);
    }
}

 

패턴을 알아내느라 조금 고생했다.

분명히 패턴이 있는데 N의 크기에 따라 달라지는 것 같았으나 다시 보나 같은 패턴을 반복하면 되는 것이었다.

 

내가 알아낸 패턴은 이렇다.

Z 모양대로의 진행방향으로 

0	1
2	3

 

의 값을 곱하여 더하는 것이다.

 

결과를 받을 변수를 result라고 할 때 해당 변수를 0으로 초기화하여 시작한다.

result + 0 * (2^N-1)^2	result + 1 * (2^N-1)^2
result + 2 * (2^N-1)^2	result + 3 * (2^N-1)^2

 

전체 배열을 같은 크기의 배열로 4등분했을 때의 각 배열의 시작 위치의 수는 위의 표와 같으며,

r과 c는 2^N-1과 비교하여 수를 구하여 해당 인덱스가 어느 배열에 포함되는지 구하면 된다.

 

따라서 N을 감소시키며 r과 c를 비교하여 어떠한 배열에 포함되는지 구하여 반복적으로 계산하면 답이 나오는 것이다.