[백준] 13549 숨바꼭질 3 - JAVA

1. 문제유형 : BFS

2. 시간복잡도 : O(NlogN) 

 

 숨바꼭질 2 와 다른 점은 순간이동 시 0초가 걸린다는 것이다. 그래서 단순히 Queue에 순차적으로 넣은 방식에서 PriorityQueue로 바꿔서 시간이 짧은 순으로 탐색해야 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int visited[] = new int[100001];
		Arrays.fill(visited, Integer.MAX_VALUE);
		PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
		q.offer(new int[]{ N, 0 });
		visited[N] = 0;
		
		int mintime = 0;
		
		while(!q.isEmpty()) {
			int[] current = q.poll();
			
			if(current[0] == K) {
				mintime = current[1];
				break;
			}
			
			for (int i = 0; i < 3; i++) {
				int num = current[0];
				if(i == 0) num += 1;
				else if(i==1) num -= 1;
				else if(i==2) num *= 2;
				
				if(num >= 0 && num <= 100000 && visited[num] >= current[1]) {
					q.offer(new int[] { num, (i==2) ? current[1] : current[1] + 1 });
					visited[num] = (i==2) ? current[1] -1 : current[1];
				}
			}
		}
		
		System.out.println(mintime);
	}

}