BOJ - 숨바꼭질 3

13549 숨바꼭질 3 : https://www.acmicpc.net/problem/13549

---

Problem

---

Solve

현재 수빈이의 위치에서 한칸씩 이동한다면 1초의 시간이 걸리고, 순간이동으로 이동한다면 0초의 시간이 걸리게됩니다.

현재 수빈이의 위치에서 이동할 수 있는 모든 경우의 수를 구하고자 한다면 시간 초과가 발생할수밖에 없습니다.

어떻게 해결해야할지 고민하다가 문제 유형이 다익스트라인것을 확인하고 접근할 수 있었습니다.

수빈이의 시작위치에서부터 앞,뒤,순간이동으로 이동할수 있는 위치에서의 최소 시간을 가져와 동생이 있는 위치까지 도달하게 해야합니다.

시작 지점부터 특정 지점까지의 최소 시간을 구하는 것이기 때문에 다익스트라로 접근이 가능하다는 것을 알게 되었습니다.

즉, 수빈이가 이동할수 있는 3가지 방법을 PriorityQueue에 저장하고 최소 시간으로 접근할 수 있는 위치를 가져와 다시 3가지 방법을 PriorityQueue에 넣어 동생의 위치까지 도달하게 구현해야합니다.

이때, PriorityQueue는 시간 기준 오름차순으로 정렬되어야합니다.

1. 최초 수빈이의 위치를 PriorityQueue에 저장합니다.
   • PriorityQueue에는 이동한 위치와 해당 위치까지 걸린 시간을 저장합니다.
2. PQ에 저장되어있는 위치 중 최소 시간을 가지는 위치를 가져옵니다.
3. 해당 위치에서 앞,뒤,순간이동 한 경우를 PQ에 저장해줍니다.
   • 단, 이동했을때 범위를 벗어나거나 방문했을 경우에는 PQ에 저장해주지 않아 중복 방문을 방지합니다.
4. PQ가 empty가 될때까지 반복합니다.

그리고 최초 수빈이의 위치가 동생의 위치보다 크거나 같다면, 뒤로 갈수 있는 경우는 한가지 경우 뿐이기 때문에 수빈 위치 - 동생 위치를 반환해줍니다.

이를 통해 O(NlogN)의 시간복잡도로 문제를 해결해줄 수 있습니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int Point = Integer.parseInt(st.nextToken());
        int Target = Integer.parseInt(st.nextToken());
        
        int time = dijkstra(Point, Target);
        
        bw.write(String.valueOf(time));
        bw.flush();
        bw.close();
    }
    
    static public int dijkstra(int Point, int Target){
    	//수빈의 위치가 동생보다 크거나 같다면 이동할 수 있는 방법은 한가지 경우
        if(Point >= Target) return Point-Target;
        
        //해당 위치 방문 여부
        boolean[] check = new boolean[100001];
        //해당 위치까지 걸리는 시간 기준 오름차순
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->{
            return o1[1]-o2[1];
        });
        
        pq.offer(new int[]{Point, 0});
        
        while(!pq.isEmpty()){
            int[] current = pq.poll();
            
            if(check[current[0]]) continue;
            
            //해당 위치가 동생의 위치라면 해당 위치까지 걸린 시간 반환.
            if(current[0] == Target) return current[1];
            
            check[current[0]] = true;
            
			//앞,뒤,순간이동시 범위를 벗어나지 않고 이동한 위치가 방문하지 않은 경우 PQ에 추가
            if(current[0]+1 < 100001 && !check[current[0]+1]){
                pq.offer(new int[]{current[0]+1, current[1]+1});   
            }
            if(current[0]-1 >= 0 && !check[current[0]-1]){
                pq.offer(new int[]{current[0]-1, current[1]+1});   
            }
            if(current[0]*2 < 100001 && !check[current[0]*2]){
                pq.offer(new int[]{current[0]*2, current[1]});
            }
        }
        
        return Target-Point;
    }
}

---

Result

힌트를 보지 않았다면 다익스트라로 풀수있을거라고 생각하지 못했었을텐데, 다익스트라의 응용을 풀어보았던것같다.

---

Reference