백준 : 13549

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

package naver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 숨바꼭질3 {
	/*
	 * 현재 시간 t
	 */
	static class Pair implements Comparable<Pair> {
		int x;
		int t;

		public Pair(int x, int t) {
			super();
			this.x = x;
			this.t = t;
		}

		@Override
		public int compareTo(Pair o) {
			return this.t - o.t;
		}
	}

	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());

		System.out.println(BFS(N, K));

	}

	public static int BFS(int n, int k) {

		int digit[] = new int[100001];	
		Arrays.fill(digit, 987654321);
		PriorityQueue<Pair> q = new PriorityQueue<Pair>();

		q.add(new Pair(n, 0));
		digit[n] = 0;

		while (!q.isEmpty()) {
			Pair cur = q.poll();
			// *2
			if (cur.x * 2 <= 100000 && digit[cur.x*2] > digit[cur.x]) {
				digit[cur.x*2] = digit[cur.x];
				q.add(new Pair(cur.x * 2, cur.t));
			}
			// 왼
			if (cur.x > 0 && digit[cur.x-1] > digit[cur.x]+1) {
				digit[cur.x-1] = digit[cur.x]+1;
				q.add(new Pair(cur.x - 1, cur.t + 1));
			}
			// 오
			if (cur.x < 100000 &&digit[cur.x+1] > digit[cur.x]+1) {
				digit[cur.x+1] = digit[cur.x]+1;
				q.add(new Pair(cur.x + 1, cur.t + 1));
			}

		}
		return digit[k];
	}
}