[Algorithm/Java] 백준 13913번 - 숨바꼭질 4

---

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

---

🔍 문제 풀이

문제 도식화

역추적을 해서 최단시간 경로를 출력해야한다.

1. 직전 노드를 parent에 기록
2. 도착점 e부터 parent를 거슬러 올라가며 갱신
3. 최단 경로 역추적

💻 코드

전체 코드

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

public class Main {
    static int[] v;

    static int s, e;
    static int[] parent = new int[200_001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<>();

        int ans = bfs();
        System.out.println(ans);

        // parent로 각 노드가 어디서 왔는지를 저장
        list.add(e);
        int idx = e;
        while(idx != s){
            list.add(parent[idx]);
            idx = parent[idx]; // e에서 출발해 parent를 따라가면서 출발점 s까지 복원
        }

        // 역추적
        for(int i= list.size()-1; i>=0; i--){
            System.out.print(list.get(i) + " ");
        }

//        System.out.println("---");
//        for(int i=0; i<parent.length; i++){
//            if(parent[i] != 0){
//                System.out.print(parent[i] + " ");
//            }
//        }


    }

    static int bfs() {
        // 1. 초기화
        Deque<Integer> dq = new ArrayDeque<>();
        v = new int[200_001];

        // 2. 초기값
        dq.offer(s);
        v[s] = 1;

        // 3. 탐색
        while(!dq.isEmpty()){
            int cur = dq.poll();
            // 3.1 종료조건
            if(cur == e) {
                return v[e] - 1;
            }

            // 3.2 3방향, next 범위
            int[] next = {cur + 1, cur - 1, cur * 2};
            for(int nx : next){
                if(nx < 0 || nx >= 200_000) continue;
                if(v[nx] == 0){
                    v[nx] = v[cur] + 1;
                    dq.offer(nx);
                    parent[nx] = cur; // nx의 직전 노드를 기록
                }
            }
        }

        return 0;
    }
}

스켈레톤 코드