BOJ (Java) 13913번: 숨바꼭질 4

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

 

 

---

풀이

0~100,000까지 갈 수 있는 배열을 선언, 해당 배열에 현재 위치에 도달하게 된 경로를 저장한다.

수빈이의 위치(N)를 시작점으로 놓고 이동해가며 다음 위치를 확인한다. 이 때 이미 해당 위치에 도달한 기록이 있다면 제외한다. (중복 제거)

현재 위치가 K에 도달한다면 탐색을 중단하고, K부터 N까지 역으로 탐색하며 경로를 출력한다.

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    private static int N, K;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");

        N = Integer.parseInt(inputs[0]);
        K = Integer.parseInt(inputs[1]);
        Queue<Integer> q = new ArrayDeque<>();

        int[] logs = new int[100_001];
        Arrays.fill(logs, -1);

        q.add(N);
        logs[N] = -2;
        
        // n + 1, n - 1, 2 * n으로 이동
        while (!q.isEmpty()) {
            Integer now = q.poll();
            if (now == K) break;
            if (now + 1 <= 100_000 && logs[now + 1] == -1) {
                logs[now + 1] = now;
                q.add(now + 1);
            }

            if (0 <= now - 1 && logs[now - 1] == -1) {
                logs[now - 1] = now;
                q.add(now - 1);
            }

            if (now * 2 <= 100_000 && logs[now * 2] == -1) {
                logs[now * 2] = now;
                q.add(now * 2);
            }
        }
        System.out.println(getCount(logs, K));
        printLog(logs, K);
    }

    // 이동 횟수 세기
    private static int getCount(int[] logs, int now) {
        if (logs[now] == -2) return 0;
        return getCount(logs, logs[now]) + 1;
    }

    // 이동한 기록 출력
    private static void printLog(int[] logs, int now) {
        if (now == -2) return;
        int bef = logs[now];
        printLog(logs, bef);
        System.out.print(now + " ");
    }
}