[BOJ-13549][다익스트라] 숨바꼭질 3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

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 숨바꼭질3 {
	static int N, K;
	static int weight[] = new int[100001];
	static PriorityQueue<Info> info=new PriorityQueue<>((o1,o2)->(o1.time-o2.time));
	public static void main(String[] args) throws IOException {
		int result=0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		Arrays.fill(weight, -1);
		weight[N]=0;
		info.add(new Info(N,0));
		
		while(!info.isEmpty()) {
			Info cur = info.poll();
			if(cur.position==K) {
				result=cur.position;
				break;
			}
			insertQueueCheck(cur.position*2, cur.time);
			insertQueueCheck(cur.position-1, cur.time+1);
			insertQueueCheck(cur.position+1, cur.time+1);
		}
		
		System.out.println(weight[K]);
	}
	private static void insertQueueCheck(int position, int time) {
		if(position>=0 && position<=100000) { //범위 안이라면?
			if(weight[position]==-1) {
				weight[position]=time;
				info.add(new Info(position,time));
			}
			else if(weight[position]>time) {
				weight[position]=time;
				info.add(new Info(position,time));
			}
		}
	}
	static class Info{
		int position;
		int time;
		public Info(int position, int time) {
			this.position = position;
			this.time = time;
		}
	}

}

소요시간 : 1시간  4분

 

 

문제를 처음봤을 때는 BFS로 접근을 했습니다. 그래서 예전에 풀었을 때는 틀렸던 문제입니다 ㅜ

하지만 최근 공부를 하다가 BFS로 최단경로를 찾을 때는 모든 가중치가 같아야 한다는 것을 알았고

다익스트라를 사용해서 다시 풀어봤습니다.

 

 

로직을 살펴보면 

1. 큐에서 현재 정보와 시간을 꺼낸다.

2. 현재 시간에서 가중치를 계산해 거리에 대한 최소값을 갱신해준다.

 

이때 우선순위큐를 사용하는데 우선순위 큐는 거리에 대한 최소값을 찾기 위해 시간이 작은 순으로 정렬해줍니다.