[백준 13549] 숨바꼭질 3 (JAVA)

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

13549번: 숨바꼭질 3

 

최소시간으로 bfs를 사용하여 문제를 풀었다.

1. 좌표와 시간을 가진 객체 생성

2. 큐 생성하여 시작 좌표 add

3. 0~100000 범위에서 +1, -1, *2한 좌표를 가진 객체를 큐에 add

4. k에 도달하였을때, 시간을 확인하여 최솟값 여부 확인 !

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static class Node{
		int x;
		int time;
		Node(int x, int time){
			this.x=x;
			this.time=time;
		}
	}
	static boolean[] visited= new boolean[100001];
	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());

		int result=Integer.MAX_VALUE;
		
		Queue<Node> q = new LinkedList<>();
		q.add(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<=100000&&!visited[x*2])
				q.add(new Node(x*2,time));
			
			if( x+1<=100000&&!visited[x+1])
				q.add(new Node(x+1,time+1));
			
			if( x-1>=0&&!visited[x-1])
				q.add(new Node(x-1,time+1));
		}
		
		System.out.println(result);
	}
}