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

bfs를 활용한 가장 빠른 시간을 찾는 문제

이동한 경로도 출력을 해야 하는데 어떻게 해야 할지 고민을 많이 했다

여태껏 visited 배열을 보통 boolean으로 true / false 로만 접근을 했었는데

 

-1로 초기화를 하고

visited 배열 값을 방문한 위치로 넣었다.

 

 

출발지 (n) 에서 목적지(m)에 도착을 한다면

m == n 이 될 때까지 재귀 호출을 통해 값을 넣어주었다

 

이는 역순으로 저장되니 선입후출 개념인 스택을 사용했고

while문 실행 전 목적지는 visited 값에 들어가지 않음으로 먼저 넣어주고

while문을 실행 하였다.

 

전체 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int visited[];
    static int dx[] = {-1,1};
    static Stack<Integer>stack = new Stack<>();
    static Queue<Node>q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String>list = new ArrayList<>();
    
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        visited = new int[1000001];
        Arrays.fill(visited, -1);
        visited[n]=n;
        q.add(new Node(n,0));
        bfs();
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node a = q.poll();
            if(a.pos==m) {
                System.out.println(a.cnt);
                stack.add(m);
                while(m!=n) {
                    stack.add(visited[m]);
                    m = visited[m];
                }
                while(!stack.isEmpty()) {
                    System.out.print(stack.pop()+" ");
                }
                break;
            }
            for(int i=0; i<3; i++) {
                int nx=0;
                if(i!=2) {
                    nx=a.pos+dx[i];
                }
                else if(i==2) {
                    nx = a.pos*2;
                }
                if(nx>=0 && nx<=100000 && visited[nx]==-1) {
                    q.add(new Node(nx,a.cnt+1));
                    visited[nx]=a.pos;
                }
            }
        }
    }
}
class Node{
    int pos,cnt;
    Node(int pos, int cnt) {
        this.pos=pos;
        this.cnt=cnt;
    }
}