[백준(Baekjoon)][자바(java)] 13549 : 숨바꼭질 3 / 최단 경로

 

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

13549번: 숨바꼭질 3

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Main {
	
	static class Dot {
		int pos, time; // pos : position
		public Dot(int pos, int time) {
			this.pos = pos;
			this.time = time;
		}
	}

	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()),
		    k = Integer.parseInt(st.nextToken());
		br.close();

		final int max = 100001; Dot dot;
		int answer = 0, pos, time, p[], t[], pos_next, time_next, i;
		
		PriorityQueue<Dot> pq = new PriorityQueue<>((d1, d2) -> 
			(d1.time == d2.time ? d1.pos - d2.pos : d1.time - d2.time)); // priority queue
		pq.add(new Dot(n, 0));

		boolean v[] = new boolean[max]; // visited
		v[n] = true;

		loop:
		while (!pq.isEmpty()) {
			dot = pq.remove();
			pos = dot.pos;
			time = dot.time;
			p = new int[]{pos * 2, pos + 1, pos - 1};
			t = new int[]{time, time + 1, time + 1};
			for (i = 0; i < 3; ++i) {
				pos_next = p[i];
				time_next = t[i];
				if (pos_next < 0 || pos_next >= max || v[pos_next])
					continue;
				if (pos_next == k) {
					answer = time_next;
					break loop;
				}
				pq.add(new Dot(pos_next, time_next));
				v[pos_next] = true;
			}
		}
		
		System.out.println(answer);
	}
}

 

아래의 두 문제와 달리 
순간 이동을 하는 경우 0초가 소요된다

또한 다익스트라로 해결하는 문제이므로
순간이동을 하는 경우의 가중치는 0(초),
한 칸 앞으로 가거나 뒤로 가는 경우의 가중치는 1(초)로 하여
우선순위 큐를 사용하여야 한다

이 때 우선순위에 대한 기준은
첫 번째로 소요시간(초)이 적은 순,
두 번째로 위치가 더 이전인 순 (소요시간이 같을 경우)

 

https://hyunjiishailey.tistory.com/157

[백준(Baekjoon)][자바(java)] 1697 : 숨바꼭질 / DFS와 BFS

https://hyunjiishailey.tistory.com/564

[백준(Baekjoon)][자바(java)] 13913 : 숨바꼭질 4 / 동적 계획법과 최단거리 역추적