백준 13913번. 숨바꼭질 4 (Java)

Problem

• 문제 링크

수빈이는 동생이랑 숨바꼭질을 하고 있습니다.

수빈이는 N 에서 시작하고 동생은 K 에 있습니다.

수빈이는 1초에 +1, -1, *2 위치로 순간이동이 가능합니다.

수빈이가 동생을 찾는 가장 빠른 시간과 이동 경로 를 구하는 문제입니다.

Solution

가장 빠른 시간은 BFS 를 이용해서 구합니다.

time 배열에 각 위치에 도달 했을 때의 시간을 저장하면 됩니다.

한번 방문한 곳은 또 방문할 필요가 없습니다.

이동 경로는 parent 배열을 사용합니다.

현재 위치 A 에서 다음 경로로 가는 방법은 3개여서 저장하기가 애매합니다.

그런데 현재 위치 A 로 이동했던 출발지는 1개입니다.

따라서 parent 배열에는 이전 경로를 저장한 뒤, 최종 도착지인 K 부터 N 까지 다시 거슬러 올라가면 됩니다.

변수	설명
time[location]	location 에 도달했을 때 시간
parent[location]	location 으로 이동하기 직전 위치

Java Code

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int[] parent = new int[100001];
    static int[] time = new int[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        bfs();

        // 순서대로 구하기 위해 stack 에 담았다가 다시 pop
        Stack<Integer> stack = new Stack<>();
        stack.push(K);
        int index = K;

        while (index != N) {
            stack.push(parent[index]);
            index = parent[index];
        }

        // 최종 출력
        sb.append(time[K] - 1 + "\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }

        System.out.println(sb.toString());
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(N);
        time[N] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();

            if (now == K) return;
            
            for (int i=0; i<3; i++) {
                int next;

                if (i == 0)         next = now + 1;
                else if (i == 1)    next = now - 1;
                else                next = now * 2;

                if (next < 0 || next > 100000) continue;

                if (time[next] == 0) {
                    q.add(next);
                    time[next] = time[now] + 1;
                    parent[next] = now;
                }
            }
        }
    }
}