[BOJ]13549_숨바꼭질3(다익스트라)

오늘은 간만에 찾아온 휴일이었다. 삼일절!

그러나 난 불쌍한 취준생이자 이번주 토욜에 정보처리기사를 봐야 하기에 꾸역꾸역 카페에 가서 공부를 하였다.

정처기만 보고 있자니, 알고리즘을 까먹을까봐 한문제만 풀자하고 저녁먹고 풀었다.

 

다익스트라 마스터가 되려 그러는지 다익스트라를 골라서 풀었다ㅋㅋ

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

13549번: 숨바꼭질 3

 

여태 연습했던 최다경로 문제와 달리, 이 문제는 그래프 문제가 아니다. 그래서 처음에 살짝 당황했지만 원리를 이해하고 있다면 푸는 방법은 똑같다.

아, 글고 문제에서 총 배열의 길이가 10만인데, 이거때문에 dist[]배열을 만들어야 하나 살짝 고민했으나, int하나가 4바이트이므로, 10만개여봤자 40만 바이트. 고로 메모리 제한으로 주어진 512MB(참고로 1메가바이트가 100만바이트..) 에는 하아아안참 모자르니 메모리 걱정은 없음으로 판단.

자 고고하자.

체크포인트

1. 10만개의 int[]인 dist를 만든다. 예를들어 dis[928]이라면 928로 이동하는데 걸린 시간을 말한다
2. 글고 visited도 만들어줄라 했다. 왜냐면 최단거리를 구하는 건데 이미 왔던곳을 또 왔다는 건 비효율적이므로 또 굳이 올 필요가 없다고 생각했다. 근데 계속 틀렸다.
   이 문제에서는 visited로 거르면 안된다. 기존의 다익스트라에서도 굳이 visited로 거를 필요가 없었는데 연산을 조금이라도 줄이려고 넣은거였다. 그래도 결과는 똑같았던 것에 비해, 지금 이 문제에서는 visited가 결과를 다르게 만든다.
3. 아무리 생각해도 왜 visited를 넣으면 결과가 달라지는지 확실히 알지 못하겠다. 아마도 비용에 0이 있기 때문이 아닌가 싶다...더 생각해보자.

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ13549_숨바꼭질3 {
	
	static class Node implements Comparable<Node>{
		int vertex;
		int cost;

		public Node(int vertex, int cost) {
			super();
			this.vertex = vertex;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int[] dist = new int[100001];
		Arrays.fill(dist, Integer.MAX_VALUE);
		boolean[] visited = new boolean[100001];
		
		dist[N] = 0;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(N, 0));
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int current = node.vertex;
//			System.out.println(Arrays.toString(dist));
//			if(current == K) break;
			
//			if(visited[current]) continue;
//			visited[current] = true;
			
			//+1
			int next1 = current+1;
			if(next1>=0 && next1<100001
					&& dist[next1]> dist[current]+1) {
				dist[next1] = dist[current]+1;
				pq.offer(new Node(next1,1));
			}
			//-1
			int next2 = current-1;
			if( next2>=0 && next2<100001 
					&& dist[next2]> dist[current]+1) {
				dist[next2] = dist[current]+1;
				pq.offer(new Node(next2,1));
			}
			//2배
			int next3 = current*2;
			if(next3>=0 && next3<100001 
					&& dist[next3]> dist[current]) {
				dist[next3] = dist[current];
				pq.offer(new Node(next3,0));
			}
		}
		
		System.out.println(dist[K]);
		
	}
}