[백준 13913 : JAVA] 숨바꼭질 4 / BFS

문제

---

 

 

 

풀이

---

최단 시간에 대해선 BFS를 통해 쉽게 알아낼 수 있다.

경로를 출력하는 부분에서 처음엔 List로 각 지점에서 거쳐온 경로를 모두 저장하는 식으로 했는데, 시간 초과로 실패했다.

 

대신, 각 지점별로 모든 경로를 저장하는게 아니라, 자신의 부모 위치만 저장한다.

 

 

 

코드

---

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, K;
    private static int[] visited = new int[100001];
    private static int[] parent = new int[100001];

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        bfs(N, K);
        System.out.println(visited[K] - 1);

        Stack<Integer> s = new Stack<>();
        int idx = K;
        while (idx != N) {
            s.push(idx);
            idx = parent[idx];
        }
        s.push(idx);

        while (!s.isEmpty()) {
            System.out.print(s.pop() + " ");
        }

        br.close();
    }

    private static void bfs(int start, int end) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = 1;

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

            if (now + 1 <= 100000 && visited[now + 1] == 0) {
                visited[now + 1] = visited[now] + 1;
                parent[now + 1] = now;
                q.add(now + 1);
            }
            if (now - 1 >= 0 && visited[now - 1] == 0) {
                visited[now - 1] = visited[now] + 1;
                parent[now - 1] = now;
                q.add(now - 1);
            }
            if (now * 2 <= 100000 && visited[now * 2] == 0) {
                visited[now * 2] = visited[now] + 1;
                parent[now * 2] = now;
                q.add(now * 2);
            }

            if (visited[end] != 0) return;
        }
    }
}