[DFS/BFS] 백준 13549번 숨바꼭질 3(Java)

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

13549번: 숨바꼭질 3

📚 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

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

예제 입력	예제 출력
5 17	2

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

📝 문제 해결

최소비용을 찾는 문제이고 해당 탐색의 가중치가 하나라서 BFS로도 해결 가능하다.
이동 방법에 따라 가중치가 다르기 때문에 이동 시간이 적은 순으로 Queue에 추가해줘야한다.

1. 탐색 시작 노드를 큐에 삽입해준다.
2. 큐에서 노드를 꺼내 해당 노드의 이동 시간이 적은 순으로 이동할 때, 이동할 점이 범위 내이고 아직 방문하지않았다면 이동 위치와 이동 시간을 큐에 삽입해준다.
3. 해당 노드의 위치가 동생의 점(K)과 일치할 때 이동 시간의 최솟값을 업데이트해준다.
4. 큐에 더 이상 탐색할 노드가 없을 때까지 반복해준다.

💻 코드

import java.io.*;
import java.util.*;
import java.awt.Point;

public class BOJ13549 {
    public static int n, k;
    public static boolean[] visited = new boolean[100001];
    public static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        bfs();
        System.out.println(result);
    }

    public static void bfs(){
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(n,0));

        while(!que.isEmpty()){
            Point p = que.poll();
            int index = p.x;
            int time = p.y;
            
            visited[index] = true;

            if(index == k) result = Math.min(result, time);
            if(index*2 <= 100000 && !visited[index*2]) que.offer(new Point(index*2, time));
            if(index+1 <= 100000 && !visited[index+1]) que.offer(new Point(index+1, time+1));
            if(index-1 >= 0 && !visited[index-1]) que.offer(new Point(index-1, time+1));
        }
    }


}