숨바꼭질 4

📍 문제 설명

 

💡 접근

자신의 부모 인덱스를 방문시 마다 입력해두고 스택 이용해서 출력하면 되는 문제

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k, answer, cnt, second;
    static int[] arr, dis = {-1, 1, 2};
    static long[] dp;
    static int[][] board;
    static int[] visited, parent;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Integer> q;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        k = kb.nextInt();
        visited = new int[100001];
        parent = new int[100001];

        System.out.println(T.solution());

        sb = new StringBuilder();

        Stack<Integer> s = new Stack<>();

        s.push(k);
        while(k != n) {
            s.push(parent[k]);
            k = parent[k];
        }
        while(!s.isEmpty()) sb.append(s.pop() + " ");
        System.out.println(sb);
    }


    private int solution() {
        q = new LinkedList<>();
        q.offer(n);
        visited[n] = 1;

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                int cx = q.poll();
                if (cx == k) {
                    return visited[cx]-1;
                }
                for (int j = 0; j < dis.length; j++) {
                    int nx = 0;
                    if(j != 2) nx = cx + dis[j];
                    else nx = cx * dis[j];
                    if (nx < 0 || nx > 100000) continue;

                    //방문하지 않은 곳만 방문
                    if(visited[nx] == 0) {
                        visited[nx] = visited[cx] + 1;
                        parent[nx] = cx;
                        q.offer(nx);
                    }
                }
            }
        }
        return 0;
    }

    private static class Point {
        private int x;
        private int second;

        public Point(int x, int second) {
            this.x = x;
            this.second = second;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", second=" + second +
                    '}';
        }
    }
}