[백준] Z (1074번)

코드 힌트

1. Z-모양 탐색:
   • 이 문제는 Z-모양으로 배열을 탐색하는 순서를 찾는 문제입니다.
   • 2차원 배열을 크기를 절반씩 줄여가며 재귀적으로 탐색합니다.
2. 배열 분할:
   • 각 호출에서 배열을 4개의 사분면으로 나누고, 목표 좌표가 속한 사분면만 재귀적으로 탐색합니다.
   • 나머지 사분면은 탐색하지 않고 그 영역의 칸 수만 더합니다.
3. 방문 순서 누적:
   • 탐색된 칸 수를 누적하여 목표 위치의 방문 순서를 계산합니다.
4. 기저 조건:
   • 재귀 호출의 기저 조건은 배열의 크기가 1일 때입니다. 이때 num을 출력합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Main {

    static int num = 0;  // 방문 순서를 저장하는 변수
    static int r, c;     // 목표 위치의 행(r), 열(c) 좌표

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 입력으로 주어진 n을 통해 2^n 크기의 배열 생성
        int n = (int) Math.pow(2, in.nextInt());  // 배열의 크기 계산 (2^n)
        r = in.nextInt();  // 목표 위치의 행(r) 입력
        c = in.nextInt();  // 목표 위치의 열(c) 입력

        // (0, 0)에서 시작하여 배열 전체를 탐색
        recursion(0, 0, n);
    }

    // Z-순서 탐색을 수행하는 재귀 함수
    public static void recursion(int x, int y, int size) {
        // size가 1이 되면 목표 위치에 도달한 것이므로 현재 방문 순서 출력
        if (size == 1) {  
            System.out.println(num);  // 목표 위치의 방문 순서 출력
            return;
        }

        // 현재 영역의 절반 크기 계산
        int half = size / 2;

        // 1. 목표 위치가 왼쪽 위 사분면에 있는 경우
        if (r < x + half && c < y + half) {
            recursion(x, y, half);  // 해당 영역으로 재귀 호출
        } else {
            num += half * half;  // 탐색하지 않은 영역의 칸 수를 누적
        }

        // 2. 목표 위치가 오른쪽 위 사분면에 있는 경우
        if (r < x + half && c >= y + half) {
            recursion(x, y + half, half);  // 해당 영역으로 재귀 호출
        } else {
            num += half * half;  // 탐색하지 않은 영역의 칸 수를 누적
        }

        // 3. 목표 위치가 왼쪽 아래 사분면에 있는 경우
        if (r >= x + half && c < y + half) {
            recursion(x + half, y, half);  // 해당 영역으로 재귀 호출
        } else {
            num += half * half;  // 탐색하지 않은 영역의 칸 수를 누적
        }

        // 4. 목표 위치가 오른쪽 아래 사분면에 있는 경우
        if (r >= x + half && c >= y + half) {
            recursion(x + half, y + half, half);  // 해당 영역으로 재귀 호출
        }
    }
}