[Gold V] 숨바꼭질 3 - 13549

문제 링크

성능 요약

메모리: 87056 KB, 시간: 228 ms

분류

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

제출 일자

2024년 8월 17일 18:41:06

문제 설명

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

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

입력

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

출력

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

풀이

java코드 복사
import java.io.*;
import java.util.*;

public class Main {
    
    static int max = 100000;
    
    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());

        boolean[] visited = new boolean[max + 1];

        // BFS를 위한 큐 초기화
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{N, 0});

        int answer = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int current = tmp[0]; // 현재 위치
            int time = tmp[1];
            visited[current] = true;

            // 동생의 위치에 도달하면 종료
            if (current == K) {
                answer = Math.min(answer, time);
            }

            // 가능한 이동
            if (current * 2 <= max && !visited[current * 2]) {
                queue.offer(new int[]{current * 2, time});
            }
            if (current + 1 <= max && !visited[current + 1]) {
                queue.offer(new int[]{current + 1, time + 1});
            }
            if (current - 1 >= 0 && !visited[current - 1]) {
                queue.offer(new int[]{current - 1, time + 1});
            }
        }
        
        System.out.println(answer);
    }
    
}