백준 1074번. Z (Java)

Problem

• 문제 링크

Z 모양으로 순회하는 순서를 알아내는 문제입니다.

Solution

처음 보는 순간 재귀가 떠오릅니다.

사각형을 4개의 사분면으로 나누어서 순서대로 들어가고 또 그 사각형 내에서 4등분 하여 접근합니다.

그렇게 사각형을 더이상 나누지 못하는 1이 될 때까지 재귀를 들어간 후에 카운트 해주면 됩니다.

(x, y, size);

(0, 0, 8);
      (0, 0, 4);
          (0, 0, 2);
              (0, 0, 1);
              (1, 0, 1);
              (0, 1, 1);
              (1, 1, 1);
          (2, 0, 2);
          (0, 2, 2);
          (2, 2, 2);
      (4, 0, 4);
          (4, 0, 2);
          (6, 0, 2);
          (4, 2, 2);
          (6, 2, 2);
      (0, 4, 4);
      (4, 4, 4);

간단하게 표현한건데 재귀에 들어가는 모습을 시각적으로 표현한 겁니다.

전부 다 나타낸 것은 아니고 일부만 나타낸 거지만 size가 1이 될 때까지 계속해서 사각형을 나누어 접근합니다.

규칙이 머리속에 바로 떠오르지 않는다면 이렇게 간단하게 적어보시면 금방 찾을 수 있습니다.

하지만 N 이 최대 15라서 재귀를 사용하며 시간 초과가 발생합니다.

시간을 줄이기 위해서 일일히 좌표에 접근하지 않고 한번에 가는 방법을 생각해보았습니다.

규칙이 보이시나요?

8 * 8 배열 일 때 각 사분면의 첫번째 값은 0, 16, 32, 48 입니다.

4 * 4 배열 일 때 각 사분면의 첫번째 값은 0, 4, 8, 12 입니다.

2 * 2 배열 일 때 각 사분면의 첫번째 값은 0, 1, 2, 3 입니다.

n * n 배열 일 때 각 사분면의 첫번째 값은

(n/2) * (n/2) * 0
(n/2) * (n/2) * 1
(n/2) * (n/2) * 2
(n/2) * (n/2) * 3

이렇게 됩니다.

count 에 대한 식을 이렇게 얻었습니다.

Exmaple

n 이 8 인 경우 (2, 3) 좌표를 찾아가보겠습니다.

Step 1. n = 8

먼저 (2, 3) 좌표는 (n / 2, n / 2) 인 (4, 4) 좌표보다 x, y 좌표가 둘다 작습니다.

그래서 왼쪽 위 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.

Step 2. n =4

그리고 다시 (2, 3) 좌표는 (n / 2, n / 2) 인 (2, 2) 좌표보다 x, y 좌표가 둘다 크거나 같습니다.

그래서 오른쪽 아래 사각형으로 이동하고 n 은 n /= 2 로 절반으로 줄어듭니다.

Step 3. n = 2

오른쪽 아래 사각형은 (2, 2) 좌표가 첫번째 값입니다.

그러므로 (2 + n / 2, 2 + n / 2) 인 (3, 3) 좌표와 값을 비교합니다.

(2, 3) 좌표는 (3, 3) 좌표보다 x 좌표는 작지만 y 좌표는 크거나 같기 때문에 오른쪽 위 사각형으로 이동합니다.

그리고 n 을 절반으로 하면 1 이 되기 때문에 더 이상 나눌 수 없고 해당 좌표의 카운트를 출력합니다.

말로 설명하기 어려운 부분이 있는데 그림을 보며 코드를 따라가시면 금방 이해할 수 있습니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    static int stoi(String s) { return Integer.parseInt(s);}

    static int N;
    static int r;
    static int c;
    static int count = 0;

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

        int N = stoi(st.nextToken());
        int r = stoi(st.nextToken());
        int c = stoi(st.nextToken());

        int n = getSize(N);
        int count = 0;
        int x = 0;
        int y = 0;

        /**
         * 사각형 절반으로 나눠서 각 사분면으로 계산
         * n 이 1 이 된다는 것은 x, y 좌표가 r, c랑 같아진다는 것
         */
        while (n > 0) {
            n /= 2;

            // 2사분면 (왼 위)
            if (r < x+n && c < y+n) {
                count += n * n * 0;
            }
            // 1사분면 (오른 위)
            else if (r < x+n) {
                count += n * n * 1;
                y += n;
            }
            // 3사분면 (왼 아래)
            else if (c < y+n) {
                count += n * n * 2;
                x += n;
            }
            // 4사분면 (오른 아래)
            else {
                count += n * n * 3;
                x += n;
                y += n;
            }

            if(n == 1) {
                System.out.println(count);
                break;
            }
        }
    }

    static int getSize(int n) {
        int result = 1;
        for(int i=0; i<n; i++) {
            result *= 2;
        }
        return result;
    }
}