백준 13913 자바 - 숨바꼭질 4 문제

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

숨바꼭질 문제의 확장으로 이전 위치를 배열에 넣어놓고 stack을 통해서 출력하게 하면 됩니다.

숨바꼭질 문제 - wellbell.tistory.com/64

랑 차이점이 거의 없어서 쉽게 해결할수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

// 숨바꼭질 4 문제 - 13913번
public class HideAndSeek4 {

    static int N, K;
    static int time;
    static boolean[] visited = new boolean[100001];
    static int[] parent = 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());
        K = Integer.parseInt(st.nextToken());

        if(N == K){
            sb.append(0).append("\n");
            sb.append(N).append("\n");
        }else {
            bfs(N);
            sb.append(time).append("\n");

            Stack<Integer> stack = new Stack<>();
            stack.add(K);
            int index = K;
            while (index != N) {
                stack.push(parent[index]);
                index = parent[index];
            }

            while (!stack.isEmpty()) {
                sb.append(stack.pop()).append(" ");
            }
        }
        System.out.println(sb);
    }

    static void bfs(int start) {
        time = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            // 만난 경우
            if(visited[K]) {
                return;
            }

            // 현재 q의 사이즈 만큼만 돌리기 - 시간 계산을 위해서
            for(int j = 0, size = q.size(); j < size; j++) {
                int now = q.poll();
                int next;

                // 다음에서 영역을 방문 처리
                // 다음의 부모를 현재로 설정
                next = now - 1;
                if(next >= 0 && !visited[next]) {
                    visited[next] = true;
                    parent[next] = now;
                    q.offer(next);
                }

                next = now + 1;
                if(next < 100001 && !visited[next]) {
                    visited[next] = true;
                    parent[next] = now;
                    q.offer(next);
                }

                next = now * 2;
                if(next < 100001 && !visited[next]) {
                    visited[next] = true;
                    parent[next] = now;
                    q.offer(next);
                }
            }
            time++;
        }
    }
}