백준 숨바꼭질3 13549 java

문제링크

문제접근

• 기존 숨바꼭질2에서 바뀐 것은 순간이동은 이동이 0초 걸린다
• 그렇다면 객체를 만들어서 위치, 시간을 기록하자

코드

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

public class baek_13549 {
    static int N,K;
    static int[] 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());
        visit = new int[100001];
        for(int i=0;i<=100000;i++){
            visit[i] = 1000000;
        }
        if(N == K){
            System.out.print(0);
            return;
        }
        bfs();
    }
    private static void bfs(){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(N,0));
        visit[N] = 0;
        int min = 10000000;
        while (!que.isEmpty()){
            Point now = que.poll();
            if(now.second >= min) continue;
            int nowP = now.place;
            int nextP;
            // 순간이동
            nextP = nowP * 2;
            if(nextP == K)  min = Math.min(min, now.second);
            else if(nextP >=0 && nextP <= 100000 && visit[nextP] > now.second){
                que.add(new Point(nextP, now.second));
                visit[nextP] = now.second;
            }
            // 걸어서 +1
            nextP = nowP + 1;
            if(nextP == K)  min = Math.min(min, now.second + 1);
            else if(nextP >=0 && nextP <= 100000 && visit[nextP] > now.second + 1){
                que.add(new Point(nextP, now.second+1));
                visit[nextP] = now.second + 1;
            }
            // 걸어서 -1
            nextP = nowP - 1;
            if(nextP == K)  min = Math.min(min, now.second + 1);
            else if(nextP >=0 && nextP <= 100000 && visit[nextP] > now.second + 1){
                que.add(new Point(nextP, now.second+1));
                visit[nextP] = now.second + 1;
            }
        }
        System.out.print(min);
    }
    private static class Point{
        int place;
        int second;
        public Point(int place,int second){
            this.place = place;
            this.second = second;
        }
    }
}

결과

정리

• 방문처리를 boolean이 아닌 int로 최단시간을 기록, 해당 시간보다 큰 시간은 방문 X
• K에서 최단시간을 min으로 갱신하며 bfs 끝난 후 min 출력