[BOJ/JAVA] 1074번: Z

1074번: Z

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

키워드

2^N× 2^N인 2차원 배열을 Z모양으로 탐색

N > 1인 경우, 배열을 크기가 2^(N-1)× 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문

---

구현

move(int y, int x, int n)

size = 2^n

1. 가장 작은 경우 size가 2^0인 경우

2. 좌상단
   1. 좌상단에 r, c의 범위가 있는 경우
      • 1/4 사이즈로 재귀호출한다.
      • 시작 위치는 좌상단이므로 동일
      • move(y, x, n - 1);
   2. 좌상단에 r, c의 범위가 없는 경우
      • 좌상단의 크기만큼 count 증가

3. 우상단
   1. 우상단에 r, c의 범위가 있는 경우
      • 1/4 사이즈로 재귀호출한다.
      • 시작 위치는 우상단이므로 x 값만 (size/2)만큼 이동
      • move(y, x + (size / 2), n - 1);
   2. 우상단에 r, c의 범위가 없는 경우
      • 우하단의 크기만큼 count 증가

4. 좌하단
   1. 좌하단에 r, c의 범위가 있는 경우
      • 1/4 사이즈로 재귀호출한다.
      • 시작 위치는 좌하단이므로 y 값만 (size/2)만큼 이동
      • move(y + (size / 2), x, n - 1);
   2. 좌하단에 r, c의 범위가 없는 경우
      • 좌하단의 크기만큼 count 증가

5. 우하단
   1. 우하단에 r, c의 범위가 있는 경우
      • 1/4 사이즈로 재귀호출한다.
      • 시작 위치는 우하단 x, y값 모두 (size/2)만큼 이동
      • move(y + (size / 2), x + (size / 2), n - 1);
   2. 우하단에 r, c의 범위가 없는 경우
      • 좌상단의 크기만큼 count 증가

---

코드

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

public class java_1074 {
    static int N;
    static int r, c;

    static int count;
    static int resultCount;

    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());

        solution();

        System.out.println(resultCount);

        br.close();
    }

    private static void solution() {
        count = 0;
        resultCount = 0;

        move(0, 0, N);

        return;
    }

    // 현재 크기를 4등분하기
    // size = 부분 행렬의 크기 -> /2값을 4등분 해야함
    private static void move(int y, int x, int n) {
        int size = (int) Math.pow(2, n);

        // 최소크기의 경우
        if (size == 1) {
            resultCount = count;
            return;
        }

        // 좌상단
        if ((x <= c && c < x + (size / 2)) && (y <= r && r < y + (size / 2))) {
            move(y, x, n - 1);
        } else {
            count += (int) Math.pow(2, 2 * n - 2);
        }

        // 우상단
        if ((x + (size / 2) <= c && c < x + (size)) && (y <= r && r < y + (size / 2))) {
            move(y, x + (size / 2), n - 1);
        } else {
            count += (int) Math.pow(2, 2 * n - 2);
        }

        // 좌하단
        if ((x <= c && c < x + (size / 2)) && (y + (size / 2) <= r && r < y + (size))) {
            move(y + (size / 2), x, n - 1);
        } else {
            count += (int) Math.pow(2, 2 * n - 2);
        }

        // 우하단
        if ((x + (size / 2) <= c && c < x + (size)) && (y + (size / 2) <= r && r < y + (size))) {
            move(y + (size / 2), x + (size / 2), n - 1);
        } else {
            count += (int) Math.pow(2, 2 * n - 2);
        }
    }

}

---

Uploaded by N2T