[백준/Gold V] 숨바꼭질 3 - 13549

[Gold V] 숨바꼭질 3 - 13549

문제 링크

성능 요약

메모리: 29348 KB, 시간: 324 ms

분류

0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2024년 11월 22일 18:28:50

문제 설명

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

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

입력

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

출력

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

 

 

제출 코드

bfs 탐색으로 최소 시간을 찾을 수 있다.

현재 위치가 X일 때 다음 위치에 대해 2*X, X-1, X+1인 지점을 순차적으로 탐색한다.

이때 위치 X에 대한 제한사항을 잘 확인하고 범위를 따지는 것이 중요하다. 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> q = new PriorityQueue<>((o1,o2)-> o1[1] - o2[1]); // {위치, 시간}을 담는다. 시간이 짧은 것 부터 dequeue
        HashSet<Integer> visit = new HashSet<>(); // q에 담긴 적 있는 위치를 저장
        q.offer(new int[]{n, 0});
        visit.add(n);
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if(cur[0] < 0 || cur[0] > 100000) continue; // 가능한 위치 범위를 벗어남.
            visit.add(cur[0]); // 방문 처리
            // 만약 현재 위치가 k와 같으면 시간 출력하고 loop 탈출
            if(cur[0] == k){
                System.out.println(cur[1]);
                break;
            }
            // x+1 로 이동. x가 k보다 작아야 의미가 있음.
            if(cur[0] < k && !visit.contains(cur[0] + 1)){
                q.offer(new int[]{cur[0]+1, cur[1] + 1});
            }
            // x-1 로 이동. x가 0보다 커야 의미가 있음.
            if(!visit.contains(cur[0]-1)){
                q.offer(new int[]{cur[0]-1, cur[1] + 1});
            }
            // 2*x로 순간이동(시간 0초 걸림). x가 k보다 작아야 의미가 있음.
            if(cur[0] < k && !visit.contains(2*cur[0])){
                q.offer(new int[]{2*cur[0], cur[1]});
            }
        }
    }
}