1074_Z

담당자

완료 여부

Solved

요약

날짜

2025/03/29

태그

재귀

난이도

출처

백준

코드

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

class Main {
    static int N, r, c;
    static int answer = 0;
    static int count = 0;
    static boolean found = false;

    // Z 모양 탐색을 어떻게 구현할 것인가
    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());

        int size = (int) Math.pow(2, N);
        zet(0, 0, size);

        System.out.println(answer);
    }

    static void zet (int x, int y, int size) {
        if (found) {
            return;
        }

        // 재귀 돌다가 현재 좌표가 목표 좌표면 재귀 종료
        if (size == 1) {
            if (x == r && y == c) {
                answer = count;
                found = true;
            }
            count++;
            return;
        }

        int half = size / 2;

        zet(x, y, half);
        zet(x, y + half, half);
        zet(x + half, y, half);
        zet(x + half, y + half, half);
    }
}
Java
복사

처음에 이렇게 했는데 시간초과가 났습니다.

타겟 좌표 (r, c)가 맵을 4등분 했을 때, 어느 사분면에 위치하는지 미리 파악 후, 해당 사분면에서만 재귀를 수행하는 식으로 수정했습니다. 중간에 재귀 조건을 헷갈려서 틀렸는데 이 부분만 조심하면 될 것 같습니다.

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

class Main {
    static int N, r, c;

    // Z 모양 탐색을 어떻게 구현할 것인가
    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());

        System.out.println(zet(N, r, c));
    }

    static int zet (int N, int r, int c) {
        if (N == 0) {
            return 0;
        }

        int half = (int) Math.pow(2, N - 1);
        int size = half * half;

        // 2사분면
        if (r < half && c < half) {
            return zet(N - 1, r, c);
        }

        // 1사분면
        else if (r < half && c >= half) {
            return size + zet(N - 1, r, c - half);
        }

        // 3사분면
        else if (r >= half && c < half) {
            return size * 2 + zet(N - 1, r - half, c);
        }

        // 4사분면
        else {
            return size * 3 + zet(N - 1, r - half, c - half);
        }

    }
}
Java
복사