백준 13913 (숨바꼭질 4) - java

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

13913번: 숨바꼭질 4

 

문제

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

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

 

유형 : BFS + 경로 역추적

 

접근 방식

• 기존 숨바꼭질 문제와 동일하게 BFS를 사용하면 된다.
• 경로에 대해서는 이전에 여러번 포스팅을 통해 설명했지만 past 배열을 사용하면 된다. past 배열에 바로 이전 지점을 저장하고 도착지에 도달했을때 첫번째 지점이 나올때까지 역추적하면 된다.
• 역추적에는 기본적으로 Stack 자료구조를 활용한다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] v = new int[100001];
    static int[] past = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());


        Queue<Integer> q = new LinkedList<>();
        v[n] = 1;
        q.add(n);

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

            if(cur == m){
                sb.append(v[cur]-1+"\n");

                Stack<Integer> stack = new Stack<>();
                int s = m;
                while(s != n){
                    stack.push(s);
                    s = past[s];
                }stack.push(n);

                while(!stack.isEmpty()){
                    sb.append(stack.pop()+" ");
                }sb.append("\n");

                System.out.print(sb);
                return;
            }

            int n1 = cur + 1;
            int n2 = cur - 1;
            int n3 = cur * 2;

            if(n1 >= 0 && n1 <= 100000){
                if(v[n1] == 0){
                    v[n1] = v[cur] + 1;
                    past[n1] = cur;
                    q.add(n1);
                }
            }

            if(n2 >= 0 && n2 <= 100000){
                if(v[n2] == 0){
                    v[n2] = v[cur] + 1;
                    past[n2] = cur;
                    q.add(n2);
                }
            }

            if(n3 >= 0 && n3 <= 100000){
                if(v[n3] == 0){
                    v[n3] = v[cur] + 1;
                    past[n3] = cur;
                    q.add(n3);
                }
            }
        }

        br.close();
    }
}