백준 13549

문제

---

방문 여부(boolean[] visited)를 체크하여

무한루프에 걸리지 않도록 하고, 가장 빠른 시간을 구할 수 있도록 함.

그리고 목적지에 도착했을 때, 정지할 수 있도록
(큐에 더 이상 저장하지 않음으로써 탐색 중지)

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P13549 {
	// 탐색용 클래스
	static class Point implements Comparable<Point> {
		int coordinate; // 현재 좌표
		int totalSecond; // 총 이동 시간(초)
		Point(int coordinate, int totalSecond) {
			this.coordinate = coordinate;
			this.totalSecond = totalSecond;
		}
		@Override
		public int compareTo(Point o) {
			return this.totalSecond - o.totalSecond;
		}
		
	}
	static boolean[] visited = new boolean[100001];
	static final int MAX = 100000; // 위치할 수 있는 좌표는 0 ~ 100000
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken()); 
		int K = Integer.parseInt(st.nextToken());
		
		bw.write(String.valueOf(bfs(N, K)));
		
		br.close();
		bw.flush();
		bw.close();
		
	}
	private static int bfs(int N, int K) {
		int result = Integer.MAX_VALUE;
		
		PriorityQueue<Point> pq = new PriorityQueue<>();
		pq.add(new Point(N, 0));
		
		while(!pq.isEmpty()) {
			Point p = pq.poll();
			int x = p.coordinate;
			int t = p.totalSecond;
			visited[x] = true;
			
			if(x == K) {
				result = Math.min(result, t);
			}
			
			if(N >= K) { 
            	// 1) 찾을 좌표가 뒤에 있으면 -1 로 가는 것이 제일 빠름
				return result = N - K;
			} else {
            	// 2) 찾을 좌표가 앞에 있을 때
                
            	// 2 - 1) 순간 이동
				if(x * 2 <= MAX && !visited[x * 2]) {
					pq.add(new Point(x * 2, t));
				}
                
                // 2 - 2)  + 1 이동
				if(x + 1 <= MAX && !visited[x + 1]) {
					pq.add(new Point(x + 1, t + 1));
				}
                
                // 2 - 3)  - 1 이동
				if(x - 1 >= 0 && !visited[x - 1]) {
					pq.add(new Point(x - 1, t + 1));
				}
			}
		}
		return result;
	}
}