[BOJ] 1074 : Z - java

문제

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

---

문제풀이

Z-order curve를 사용하여 2차원 공간에서 특정 위치를 찾는 문제이다. Z-order curve는 2차원 좌표를 재귀적으로 분할하여 각 분할 영역에 번호를 매기는 방식으로, 각 좌표의 비트를 번갈아가며 결합하여 1차원으로 정렬한다. 문제는 N x N (2^N x 2^N) 크기의 격자에서 Z-order를 따라 (r, c) 위치를 방문하는 순서를 찾는 것이다.

2^N x 2^N인 2차원 배열을 사분면으로 축소해 가며 (r, c)가 어느 작은 격자에 속하는지 재귀적으로 탐색을 한다.

x 좌표 : r >= x && r < x + len / y 좌표 : c >= y && c < y + len
위와 같은 조건으로 x = 0, y = 0의 값으로 시작해 재귀적으로 탐색을 하면 가작 작은 범위의 사분면부터 z모양으로 탐색을 하는 로직이다.

조건에 해당되지 않을 시 탐색한 사분면에 해당되지 않으니 넓이만큼 seq 값을 쌓는다.
탐색하는 (x,y) 값이 (r,c)와 같을 경우 쌓인 seq 값을 출력하고 종료한다.

---

소스코드

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

public class _1074 {
    static int N, r, c;
    static int seq = 0;

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

        z(0, 0, (int) Math.pow(2, N));
        br.close();
    }
    static void z(int x, int y, int len) {
        if (x == r && y == c) {
            System.out.println(seq);
            return;
        }
        if ((r >= x && r < x + len) && (c >= y && c < y + len)) {
            // x,y 좌표가 특정 사분면에 포함되는 경우 면적 축소
            int nowLen = len / 2;
            z(x, y, nowLen); // 좌상단
            z(x, y + nowLen, nowLen); // 우상단
            z(x + nowLen, y, nowLen); // 좌하단
            z(x + nowLen, y + nowLen, nowLen); // 우하단
        } else {
            // x,y 좌표가 특정 사분면에 포함되지 않는 경우 해당 사분면 넓이만큼 축적
            seq += (int) Math.pow(len, 2);
        }
    }
}

---

etc

알고리즘이 분할 정복, 재귀로 분류된 문제였다. 재귀적 분할 정복 기법을 사용하여 시간 및 공간 복잡도에 대한 효율성 있게 활용할 수 있는 공부가 필요하다고 느꼈다.

https://djun95.tistory.com/10

Z-order 탐색 알고리즘