[백준] 13549 숨바꼭질 3 - BFS JAVA

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

13549번: 숨바꼭질 3

 

문제풀이

BFS를 활용합니다.

최소비용을 찾는 문제이기에 순간이동을 하는것이 가장 먼저 수행되어야 합니다. (순간이동은 0초가 걸림)

여기서 최소비용은 시간을 의미합니다.

그러기 위해, 문제에서 가장 빠르게 계산하기 위해 우선순위를 두어서 진행합니다.

큐에 들어가서 모든 경우를 다 체크하므로 우선순위를 두어서 진행하지 않아도 됩니다. 

 

일반적인 BFS는 도달하는 점에 도착하면 종료되지만,

이번 문제는 모든 경우를 다 탐색하므로 Queue에 모든 경우의 수를 넣습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static int N,K;
	public static boolean[] visited;
	public static int result = Integer.MAX_VALUE;
	public static int max = 100000;
	public static Queue<Node> q = new LinkedList<>();
    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());
    	
    	visited = new boolean[max + 1];
    	bfs();
    	System.out.println(result);
    }
    
    public static void bfs() {
    	q.offer(new Node(N,0));
    	while(!q.isEmpty()) {
    		Node node = q.poll();
    		int x = node.x;
    		int time = node.time;
    		visited[x]= true;
    		
    		if(x == K) result = Math.min(result,  time);
    		
    		if(x * 2 <= max && visited[x * 2] == false) q.offer(new Node(x * 2, time)); //순간이동할경우 0초의 시간이 걸립니다.
    		if(x + 1 <= max && visited[x + 1] == false) q.offer(new Node(x + 1, time + 1)); //걷기는 1초
    		if(x - 1 >= 0 && visited[x - 1] == false) q.offer(new Node(x - 1, time + 1)); //걷기는 1초
    	}
    }
    
    
    
}

class Node{
	int x;
	int time;
	public Node(int x , int time) {
		this.x=x;
		this.time = time;
	}
}