[백준] 1074. Z (분할 정복/Java)

[백준] 1074. Z

 

📌 풀이 과정

4  × 4  크기의 배열을 방문한 순서

 

초기 접근 방식

2^(N-1) × 2^(N-1) 크기의 2차원 배열을 만들어서 Z순서를 기록하고 (r,c)의 값을 찾는 방식으로 접근했다.

하지만 N = 15인 경우, 2^14 × 2^14 크기의 배열이 필요하기 때문에 메모리 초과가 발생했다.

하하!!! 크리스마스 이브날에 푼 문제라 그런지 어떻게 재귀로 이끌어내야 할지 머리가 안돌아갔다...

 

분할 정복

N = 2 인 경우

0	1
2	3

 

N = 3 인 경우

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

 

N = 4 인 경우

 

N이 1 커질 때마다 사분면의 크기는 2배씩 커지고
배열을 4등분한 각 사분면은 이전 크기의 Z 방문 순서를 그대로 따른다는 것을 알 수 있다.

 

1. 현재 좌표 (r, c)가 어느 사분면에 위치하는지 찾는다.

배열을 4등분했을 때

1사분면(좌상), 2사분면(우상), 3사분면(좌하), 4사분면(우하) 중 어디에 있는지 확인한다.

 

2. 앞선 사분면들에서 이미 방문한 칸의 개수를 answer에 더한다.

• 2사분면에 있다면: 1사분면의 칸 개수만큼 더하기
• 3사분면에 있다면: 1사분면 + 2사분면의 칸 개수만큼 더하기
• 4사분면에 있다면: 1사분면 + 2사분면 + 3사분면의 칸 개수만큼 더하기

3. 다음 재귀 호출을 위해 좌표를 변환한다.

해당 사분면을 새로운 배열로 보고, 그 배열에서의 좌표로 바꿔준다.

예: 8x8 배열의 (5,3) → 3사분면의 4x4 배열에서 (1,3)

 

4. 배열 크기를 절반으로 줄이고 재귀 호출한다.

1x1 배열이 될 때까지 반복하면, answer에 누적된 값이 최종 방문 순서가 된다.

 

✨ 제출 코드

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

public class Main {
    static int N, r, c;
    static int ans = 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());

        solve(0, 0, (1 << N));
    }

    private static void solve(int x, int y, int size) {
        if (size == 1) {
            System.out.println(ans);
            return;
        }

        int newSize = size / 2;

        if (r < x + newSize && c < y + newSize) {
            solve(x, y, newSize);
        }
        else if (r < x + newSize && c >= y + newSize) {
            ans += (newSize * newSize);
            solve(x, y + newSize, newSize);
        }
        else if (r >= x + newSize && c < y + newSize) {
            ans += (newSize * newSize * 2);
            solve(x + newSize, y, newSize);
        }
        else {
            ans += (newSize * newSize * 3);
            solve(x + newSize, y + newSize, newSize);
        }
    }
}