백준 숨바꼭질4 13913 java

문제링크

문제 접근

• 숨바꼭질 시리즈에서 추가된 것은 경로까지 출력
• 객체에 String으로 경로 추가하면서 bfs 돌자

코드

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

public class baek_13913 {
    static int N, K;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if(N == K){
            System.out.println(0);
            System.out.print(N);
            return;
        }
        else if(N > K){
            StringBuilder sb = new StringBuilder();
            for(int i=N;i>K;i--){
                sb.append(i + " ");
            }
            sb.append(K);
            System.out.println(N-K);
            System.out.print(sb);
            return;
        }
        visit = new boolean[100001];
        bfs();
    }
    private static void bfs(){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(N,N+" "));
        visit[N] = true;
        int time = 0;
        while (!que.isEmpty()){
            int size = que.size();
            for(int s=0;s<size;s++){
                Point now = que.poll();
                int nowP = now.point;
                int nextP;
                // 순간이동
                nextP = nowP * 2;
                if(nextP == K){
                    System.out.println(time + 1);
                    System.out.print(now.course + nextP);
                    return;
                }
                else if(nextP>=0 && nextP<=100000 && !visit[nextP]){
                    que.add(new Point(nextP, now.course + nextP + " "));
                    visit[nextP] = true;
                }
                // 걷기 +1
                nextP = nowP + 1;
                if(nextP == K){
                    System.out.println(time + 1);
                    System.out.print(now.course + nextP);
                    return;
                }
                else if(nextP>=0 && nextP<=100000 && !visit[nextP]){
                    que.add(new Point(nextP, now.course + nextP + " "));
                    visit[nextP] = true;
                }
                // 걷기 -1
                nextP = nowP - 1;
                if(nextP == K){
                    System.out.println(time + 1);
                    System.out.print(now.course + nextP);
                    return;
                }
                else if(nextP>=0 && nextP<=100000 && !visit[nextP]){
                    que.add(new Point(nextP, now.course + nextP + " "));
                    visit[nextP] = true;
                }
            }
            time++;
        }
    }
    private static class Point{
        int point;
        String course;

        public Point(int point, String course) {
            this.point = point;
            this.course = course;
        }
    }
}

결과

정리

• 시간 초과가 났었는데 이유는 입력이 100000 0 처럼 N > K 일 때는 경로가 딱 한 개이므로 bfs 돌 필요없고 출력만 바로 하면 된다.
• 또한 순간이동 -> 걷기 +1 -> 걷기 -1 순으로 bfs 돌기