13549번 : 숨바꼭질 3 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(14분 30초)

아이디어

일단 그래프 탐색을 통해서 수빈이가 동생을 최단 시간 안에 찾을 수 있도록 하려 했다.
그때 고민한 것은 DFS냐 BFS냐 였는데
DFS로 했을때는 시간이 depth이고 DFS를 수행했을때
일단 해당 시간대에 다른 성공 할 수 있는 경우는 뒷전이고
주구장창 막히거나 도착할때까지 쓸데없는 연산을 반복하게 됨으로

해당 문제에서 너비(time)를 우선적으로 탐색하여 앞선 시간에서 도착하면 끝낼 수 있는 효율적인 BFS로 작성을 해보았다.

수빈이가 이동하는 경우는

3가지이다.

1. x->2x로 순간이동, 시간 추가 X
2. x->x+1로 이동, 시간 +1
3. x->x-1로 이동, 시간 -1
   이때 주의할 것은
   1번의 경우에는 시간이 추가되지 않음으로
   2,3번 처럼 큐의 add를 통해 뒤쪽에 쌓아두면
   더 긴 시간에서의 성공에 대한 정보를 획득하고 먼저 끝나버리는 문제가 발생함으로
   addFirst로 큐의 앞에다 넣어준다.

그리고 각 이동별 x가 범위를 벗어나지 않게 + 해당 x로 도착했던 경우 중에 지금이 최고라면
q에 넣어주고 visited도 갱신해주도록 하면 끝이다.

풀이코드

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int [] visited = new int[100001];
        ArrayDeque<int []> q = new ArrayDeque<>();
        Arrays.fill(visited, Integer.MAX_VALUE);
        visited[N] = 0;
        q.add(new int[]{N, 0});
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int loc = cur[0];
            int time = cur[1];
            if(loc==K){
                System.out.print(time);
                return;
            }
            if(loc*2<=100000 && visited[loc*2]>time){
                q.addFirst(new int[]{loc*2, time});
                visited[loc*2] = time;
            }
            if(loc+1<=100000&&visited[loc+1]>time+1){
                q.addLast(new int[]{loc+1, time+1});
                visited[loc+1] = time+1;
            }
            if(loc-1>=0&&visited[loc-1]>time+1){
                q.addLast(new int[]{loc-1, time+1});
                visited[loc-1] = time+1;
            }
        }
    }
}