숨바꼭질4

📍 문제 설명

 

💡 접근

2 문제와는 다르게 가짓수가 아닌 이동하는 경로를 출력하는 문제다.

다음지점의 인덱스에 현지점(부모) 인덱스를 집어넣고

스택에 해당 값들을 거꾸로 넣어놓고 출력하면된다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max, min, L, R, C = Integer.MAX_VALUE;
    static int[][] board;
    static int[] dis = {-1,1,2};
    static int[] visited = new int[100001];
    static int[] parent = new int[100001];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //수빈이 위치
        m = kb.nextInt(); //동생 위치

        T.solution(n);

        System.out.println(visited[m] - 1);

        Stack<Integer> s = new Stack<>();
        s.push(m);

        int index = m;
        while (index != n) {
            s.push(parent[index]);
            index = parent[index];
        }
        while(!s.isEmpty()){
            System.out.print(s.pop() + " ");
        }


    }

    private void solution(int n) {
        Queue<Integer> q = new LinkedList<>();
        //수빈이 지점 넣어놓기
        q.offer(n);
        //경과 시간
        visited[n] = 1;

        while(!q.isEmpty()) {
            int len = q.size();//1 3 9
            for(int i = 0; i < len; i++) {
                int cx = q.poll();

                if(cx == m) return;

                //3가지 방향으로 이동(x-1, x+1, 2*x)
                for(int j = 0; j < 3; 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) {
                        q.offer(nx);
                        visited[nx] = visited[cx] + 1;
                        parent[nx] = cx;
                    }
                }
            }
        }
    }


}