[백준 1074] Z(G5) — 재귀로 방문 순서 계산하기

[G5] 1074 Z 문제 바로 가기

 

 

 

1. 문제 요약

정수 N, R, C가 주어졌을 때,

 

2^N × 2^N 배열을 Z 모양 순서로 방문한다고 하면

좌표 (R, C)는 몇 번째(0-index) 로 방문되는지 출력하는 문제다.

 

여기서 핵심은 배열을 진짜로 만들고 순회하면 절대 안 된다는 점이다.

2^N은 N이 커질수록 급격히 커지고, 모든 칸을 직접 방문하면 시간/메모리가 터진다.

---

 

2. 처음 시도: 전체를 돌면 왜 망할까?

가장 흔한 실수는 이런 접근이다.

• 실제 2^N × 2^N 배열 생성
• Z 순서대로 하나씩 방문하면서 카운트 증가
• (R,C) 도달하면 출력

왜 안 되냐면, 칸 수가 2^(2N)개라서

N이 조금만 커져도 탐색 자체가 “물리적으로” 불가능해진다.

 

즉, 이 문제는 “탐색” 문제가 아니라

(R,C)가 속한 위치가 Z 순서에서 몇 번째인지 “계산”하는 문제다.

---

3. 문제 핵심 [1]: “사분면 단위로 쪼개라” (분할정복)

Z 순서는 항상 사분면 기준으로 진행된다.

 

문제에서 Z 규칙이 좌상, 우상, 좌하,우하 순서로 진행하므로 아래와 같이 정의한다.

1. 1사분면(좌상)
2. 2사분면(우상)
3. 3사분면(좌하)
4. 4사분면(우하)

그리고 각 사분면은 전체의 정확히 1/4 크기다.

 

한 변 길이가 size라면,

• 전체 칸 수: size * size
• 사분면 한 개 칸 수: size * size / 4

즉, (R,C)가 어느 사분면에 있느냐에 따라

그 전에 이미 방문된 칸 수를 한 번에 더할 수 있다.

• 1사분면이면: + 0
• 2사분면이면: + 1 * (size*size/4)
• 3사분면이면: + 2 * (size*size/4)
• 4사분면이면: + 3 * (size*size/4)

그리고 나서 해당 사분면 내부로 들어가서, 좌표를 그 사분면 기준으로 바꿔서 다시 반복한다.

 

이게 분할정복이다.

---

4. 문제 핵심 [2]: 좌표를 “사분면 내부 좌표”로 변환해야 한다.

사분면으로 들어갈 때, (R,C)는 그대로 쓰면 안 되고

“선택된 사분면 안에서의 좌표”로 바꿔야 한다.

 

예를 들어 size/2가 반쪽 길이라고 하면:

• 2사분면(우상): c -= size/2
• 3사분면(좌하): r -= size/2
• 4사분면(우하): r -= size/2, c -= size/2
• 1사분면(좌상): 변환 없음

이 과정을 해야 “작아진 배열” 안에서 계속 같은 규칙을 적용할 수 있다.

 

 

5. 최종 풀이 코드 (완성본)

아래 코드는 배열을 만들지 않고,

사분면을 따라 내려가며 count에 “건너뛴 칸 수”를 누적하는 방식이다.

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

public class Main {
    static int count;

    public static void main(String[] args) throws IOException {
        int N, R, C;
        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());

        int size = (int) Math.pow(2, N); // 한 변의 길이
        find(size, R, C);

        System.out.println(count);
    }

    // 2^N * 2^N 배열에서 (r, c)를 방문하는 순서를 계산하는 함수
    public static void find(int size, int r, int c) {
        // Base condition: size가 1이면 더 쪼갤 필요 없음
        if (size == 1) return;

        int half = size / 2;
        int quadrantSize = (size * size) / 4; // 한 사분면이 갖는 칸 수

        // 1사분면 (좌상)
        if (r < half && c < half) {
            find(half, r, c);

        // 2사분면 (우상)
        } else if (r < half && c >= half) {
            count += quadrantSize;
            find(half, r, c - half);

        // 3사분면 (좌하)
        } else if (r >= half && c < half) {
            count += quadrantSize * 2;
            find(half, r - half, c);

        // 4사분면 (우하)
        } else {
            count += quadrantSize * 3;
            find(half, r - half, c - half);
        }
    }
}

---

6. 동작 방식 예시로 이해하기

예를 들어 어떤 단계에서 size=8이고 (R,C)가 4사분면(우하) 라고 해보자.

 

그럼 4사분면은 1~3사분면을 전부 방문한 뒤 시작하므로

• 사분면 한 개 칸 수 = 8*8/4 = 16
• 4사분면 전에 방문한 칸 수 = 16 * 3 = 48

즉, count += 48을 하고,

이제 size=4짜리 우하 사각형 안에서 다시 같은 작업을 반복한다.

 

이걸 계속 내려가면, 결국 (R,C)의 정확한 방문 순서가 나온다.

---

7. 결론: 1074는 “사분면 스킵 + 분할정복” 문제다

이 문제는 Z 모양을 “그대로 따라가며 시뮬레이션”하는 게 아니라,

• (R,C)가 속한 사분면을 빠르게 판단하고
• 그 전에 방문되는 칸 수를 한 번에 누적한 뒤
• 좌표를 사분면 내부 좌표로 바꿔서 반복하는

전형적인 분할정복/재귀 계산 문제다.

• 전체 순회로 풀면: 시간/메모리 둘 다 터짐
• 사분면으로 쪼개면: 매 단계마다 size가 반으로 → 재귀 깊이 O(N)
• 즉, 배열 없이도 정답을 “계산”할 수 있다.