[백준] 13549 - 숨바꼭질 3 (자바 Java)

[Gold V] 숨바꼭질 3 - 13549

문제 링크

성능 요약

메모리: 23028 KB, 시간: 216 ms

분류

0-1 너비 우선 탐색(0_1_bfs), 너비 우선 탐색(bfs), 다익스트라(dijkstra), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

다익스트라 알고리즘을 통해 최단경로를 찾도록 했다.

고민했던 부분은 두 가지가 있는데,

1. 다익스트라는 한 정점에서 연결된 다른 정점에서의 거리가 가장 짧은 것부터 검사하기 때문에 N*2만 검사하다 보면 시간이 과하게 소요되지 않을까 생각했다. 그러나 어차피 최대가 100,000이라 크게 시간이 소요되지 않아서 괜찮았다.

 

2. 0보다 작고 100,000보다 큰 경우의 수도 고려해야 하나 생각했다.

0보다 작은 경우는 -1, -2 등이 있는데 N과 K가 모두 0이상이기 때문에 -1. -2를 거쳐가는 경우는 최단경로일 수 없다.

100,000보다 큰 경우도 고려했으나

50,001 100,000인 경우 

50,001 -> 100,002 -> 100,001 -> 100,000 보다

50,001 -> 50,000 -> 100,000 이 더 빠르기 때문에 고려할 필요가 없다.

 

그래서 N*2, N-1, N+1이 0보다 크거나 같고 100,000보다 작다면 우선순위 큐에 넣어준다.

큐에서 경로를 갱신하는 과정은 해당 index가 배열의 범위 내에 있을 때 dist[idx]가 dist[start]에서 1 또는 0 (값에 따라)을 더한 값보다 크다면 작은 값으로 갱신한다.

갱신이 잘 이루어지게 하기 위해 배열의 초기값을 Integet.MAX_VALUE로 초기화한다.

package BOJ.Gold.g5;

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

public class BOJ_13549_숨바꼭질3 {

	static class Edge implements Comparable<Edge> {
		int st;
		int ed;
		int dist;

		public Edge(int st, int ed, int dist) {
			this.st = st;
			this.ed = ed;
			this.dist = dist;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.dist - o.dist;
		}
	}

	static final int MAX = 100000;
	static boolean[] visited = new boolean[100001];
	static int[] dist = new int[100001];
	static int N, K;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		Arrays.fill(dist, Integer.MAX_VALUE);
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		// N에 연결된 edge 3개 추가

		// 0보다 작은 경우는 최소값이 될 수가 없음
		// 100,000보다 큰 경우도 마찬가지임
		/*
		 * 최대가 100인 경우 51 100 51 - 102 - 101 - 100 보다 51 - 50 - 100 이 더 빠르기 때문
		 * 0~100,000까지만 고려하면 된다
		 */
		dist[N] = 0;
		if (N - 1 >= 0) {
			pq.add(new Edge(N, N - 1, 1));
			dist[N - 1] = 1;
		}
		if (N + 1 <= MAX) {
			pq.add(new Edge(N, N + 1, 1));
			dist[N + 1] = 1;
		}
		if (N * 2 <= MAX) {
			pq.add(new Edge(N, 2 * N, 0));
			dist[N * 2] = 0;
		}

		// dijkstra
		while (!visited[K]) {
			Edge e = pq.poll();
			if (visited[e.ed])
				continue;

			visited[e.ed] = true;
			// ed*2
			if (e.ed * 2 <= MAX && dist[e.ed * 2] > dist[e.ed])
				dist[e.ed * 2] = dist[e.ed];

			if (e.ed * 2 <= MAX)
				pq.add(new Edge(e.ed, e.ed * 2, dist[e.ed * 2]));
			// ed-1
			if (e.ed - 1 >= 0 && dist[e.ed - 1] > dist[e.ed] + 1)
				dist[e.ed - 1] = dist[e.ed] + 1;
			if (e.ed - 1 >= 0)
				pq.add(new Edge(e.ed, e.ed - 1, dist[e.ed - 1]));

			// ed+1
			if (e.ed + 1 <= MAX && dist[e.ed + 1] > dist[e.ed] + 1)
				dist[e.ed + 1] = dist[e.ed] + 1;
			if (e.ed + 1 <= MAX)
				pq.add(new Edge(e.ed, e.ed + 1, dist[e.ed + 1]));

		}
		System.out.println(dist[K]);
	}

}