[백준] 13913번 : 숨바꼭질 4

13913번: 숨바꼭질 4

---

[BFS]

백준의 숨바꼭질 시리즈 중 4번 째 문제. 이번에는 1초 뒤 -1, +1, *2 칸으로 이동할 수 있고, end에 도착했을 때 최소 시간과 그 때의 거쳐온 과정을 나열한다. 과정을 출력하는 것은, from[]이라는 배열을 준비하고, cur정점에서 next 정점으로 n만큼의 시간을 거쳐서 갈 때, 

from[next] = cur

arr[next] = n

visit[next] =true 한다.

 

이렇게 저장된 from[]에서 필요한 것만 빼서 List에 저장 후 역순으로 출력하면 끝

# Code </>

public class Main {

    static class Element{
        int next, dist;
        public Element(int n, int d){
            next = n;
            dist = d;
        }
    }
    static final int N = 100001;
    static boolean[] visit = new boolean[N];
    static int[] arr = new int[N], from = new int[N], move = {-1, 1, 0};

    static void BFS(int start, int end){

        Queue<Element> Q = new LinkedList<>();
        visit[start] = true;
        Q.add(new Element(start, 0));

        while(!Q.isEmpty()){
            Element e = Q.poll();

            int current = e.next;
            int dist = e.dist;

            if(current == end) break;

            move[2] = current;
            for(int a=0; a<3; a++){
                int next = current + move[a];

                if(next < 0 || next > N-1 || visit[next]) continue;

                visit[next] = true;
                arr[next] = dist + 1;
                from[next] = current;
                Q.add(new Element(next, dist + 1));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        List<Integer> list = new ArrayList<>();

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        BFS(start, end);

        list.add(end);
        int v = end;
        while(v != start){
            list.add(from[v]);
            v = from[v];
        }

        System.out.println(arr[end]);
        for(int i=list.size()-1; i>=0; i--)
            System.out.print(list.get(i) + " ");
    }
}