[ 백준 / 자바 ] 13549. 숨바꼭질3

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

13549번: 숨바꼭질 3

---

---

📑 문제

수빈이가 현재 있는 위치 N에서 동생이 있는 위치 K까지 가는데 필요한 가장 빠른 속도를 출력하라

• 수빈이의 위치가 X일 때
  • 걷기 : X-1, X+1 위치로 이동할 수 있다. 이동 시 1초의 시간이 소요된다.
  • 순간이동 : X*2 위치로 이동할 수 있다. 이동 시 0초의 시간이 소요된다.

💡 입력

✔ 수빈이가 있는 위치 N

✔ 0 ≤ N ≤ 100,000

✔ 동생이 있는 위치 K

✔ 0 ≤ K ≤ 100,000

---

---

✨ 풀이과정

✔ 우선순위큐를 사용한 데이크스트라(다익스트라)를 구현한다

💥 반복문을 사용한 데이크스트라는 시간초과가 난다

 

---

---

📑 코드

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

public class D5_13549_숨바꼭질3 {

	static int N;// 수빈이의 현재 위치
	static int K; // 동생 위치
	static boolean[] check;
	static int[] dist; // 시작위치 -> K까지 가는 최단시간
	static int INF = Integer.MAX_VALUE;
	static int ans; // 최단위치

	public static class Node implements Comparable<Node> {

		int idx, cost;

		public Node(int idx, int cost) {
			super();
			this.idx = idx;
			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);

		N = sc.nextInt(); // 시작정점
		K = sc.nextInt(); // 도착정점

		dist = new int[100001]; //시간 저장

		Arrays.fill(dist, INF);
		
		//////////초기화

		ans = 0; //최소 시간이 몇 초인지
		dikstra(N); //시작점에서 출발~

		System.out.println(ans);

	}

	//반복문 다익스트라로 풀면 시간초과 난다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	private static void dikstra(int N) {

		PriorityQueue<Node> pq = new PriorityQueue<>(); 

		check = new boolean[100001]; //출발 노드였는지 체크

		pq.add(new Node(N, 0)); //시작점
		dist[N] = 0; //동생한테 가기까지 걸리는 최소시간 저장

		while (!pq.isEmpty()) {
			Node curr = pq.poll(); //최소시간부터 폭폭 튀어나오게 해봅시당

			if (check[curr.idx]) //이미 이미 내가 갔던 위치다
				continue; //넘어가

			if (curr.idx == K) { //내가 가야 할 위치(동생의 위치)다!
				//pq이므로 K에 도달하는 경우 중 제일 적은 시간이 먼저 튀어나오므로 
				ans = dist[curr.idx]; //정답입니다~				
				return;
			}

			check[curr.idx] = true; //지금부터 idx 위치에서 -1 +1, *2 가볼것
			dist[curr.idx] = curr.cost; //시간은 내 위치가 가지고 있는 시간으로 설정
			

			//순간이동
			// 2의 배수 처리 
			if (curr.idx != 0) {
				for (int k = curr.idx * 2; k < (dist.length); k *= 2) { // *2씩 가야 함 
					dist[k] = dist[curr.idx]; //순간이동은 시간이 0초 걸리므로 지금 위치와 시간이 같다
					pq.add(new Node(k, dist[k])); //pq에 추가
				}
				
			}
			
			
			//걸을 때
			if ((curr.idx - 1) >= 0 && !check[curr.idx - 1] && dist[curr.idx - 1] > dist[curr.idx] + 1) { //현재 위치-1이 0보다 크고, 방문하지 않았고, idx-1에 원래 있던 시간이 현재 위치가 가진시간+1 보다 크면
				//갱신할게용
				dist[curr.idx - 1] = dist[curr.idx] + 1;
				pq.add(new Node(curr.idx - 1, dist[curr.idx - 1]));
			}

			// idx+1 갱신
			if ((curr.idx + 1) < dist.length && !check[curr.idx + 1] && dist[curr.idx + 1] > dist[curr.idx] + 1) {
				dist[curr.idx + 1] = dist[curr.idx] + 1;
				pq.add(new Node(curr.idx + 1, dist[curr.idx + 1]));
			}

		}

	}// dikstra
}

 

---

---