[백준/JAVA] BOJ 13913 - 숨바꼭질 4

bfs 문제를 풀어보자! 근데 이제 역추적...을 곁들인

👀 문제

13913번: 숨바꼭질 4 ✨ 골드 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

예제 입력

5 17

예제 출력

4
5 4 8 16 17

🔑 키포인트

너비 우선 탐색 역추적

✍️ 코드

📍 시간초과를 유의해야 하는 문제

🤔 처음에 경로를 저장하는 방식으로 String을 이용해 Node의 매개변수 중 하나로 받아서 저장하고, String에 계속해서 경로를 더해 주는 방식을 사용했다. 이는 O(N)의 시간복잡도를 가지기 때문에 시간 초과를 유발할 수 있다! (실제로 46%에서 시간초과 발생함 ㅠㅠ)

💡 root[]라는 배열을 만들어서 root[1] = 2 => 1에 도착하기 전에 있었던 위치는 2 이런 식으로 저장해서 시간초과를 해결했습니다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ13913_숨바꼭질4 {
    static int n, k;
    static int[] dx = { 1, -1, 2 };
    static boolean[] visited;
    static int[] root;
    static Queue<Node> q;

    static class Node {
        int idx, time;

        Node(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
    }

    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());
        k = Integer.parseInt(st.nextToken());
        q = new LinkedList<>();
        q.add(new Node(n, 0));

        visited = new boolean[200002];
        root = new int[200002];
        visited[n] = true;
        bfs();
    }

    static void bfs() {
        while (!q.isEmpty()) {
            Node now = q.poll();
            int x = now.idx;
            if (x == k) {
                System.out.println(now.time);
                Stack<Integer> path = new Stack<>();
                for (int i = k; i != n; i = root[i]) {
                    path.push(i);
                }
                path.push(n);
                StringBuilder sb = new StringBuilder();
                while (!path.isEmpty()) {
                    sb.append(path.pop() + " ");
                }
                System.out.println(sb.toString());
                break;
            }

            for (int i = 0; i < 3; i++) {
                int nx = x + dx[i];
                if (i == 2) {
                    nx = x * dx[i];
                }
                if (isValid(nx)) {
                    visited[nx] = true;
                    q.add(new Node(nx, now.time + 1));
                    root[nx] = x;
                }
            }

        }
    }

    static boolean isValid(int x) {
        if (x >= 0 && x < 200002 && !visited[x]) {
            return true;
        }
        return false;
    }
}