문제 풀이

숨바꼭질 2와는 다르게 순간이동 소요시간이 0초다.
그냥 cur_pos(현재 위치)가 k일때 큐에 담고있는 pos(위치), cnt(소요시간) 정보를 이용해서
가장 최소 소요 시간을 갱신하며 마지막에 출력하면된다.

문제 링크

boj/13549

소스코드

PS/13549.java

  
    import java.io.*;
    import java.util.*;

    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        static class Entity
        {
            int cnt;
            int pos;

            public Entity(int cnt, int pos) {
                this.cnt = cnt;
                this.pos = pos;
            }
        }
        static int []visit = new int [100001];
        static int []cnt = new int [100001];
        public static void main(String[] args) throws IOException {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            Queue<Entity> q = new LinkedList<>();
            q.add(new Entity(0,n));
            int min =987654321;
            while(!q.isEmpty())
            {
                int cur_pos = q.peek().pos;
                int cur_cnt =  q.peek().cnt;
                q.poll();
                if(cur_pos ==k && cur_cnt < min) {
                    min= cur_cnt;
                }
                visit[cur_pos] = 1;
                if(cur_pos *2 <=100000&&visit[cur_pos * 2] == 0 ) {
                    q.add(new Entity(cur_cnt,cur_pos * 2));
                }
                if( cur_pos + 1 <= 100000 && visit[cur_pos +1] ==0 ) {
                    q.add(new Entity(cur_cnt + 1,cur_pos + 1));
                }
                if( cur_pos -1 >=0 && visit[cur_pos - 1] ==0 ) {
                    q.add(new Entity(cur_cnt + 1,cur_pos - 1));
                }


            }
            bw.write(Integer.toString(min));
            bw.flush();
            
        }
    }