[BaekJoon] 12851 숨바꼭질 2 (Java)

1.  문제 링크

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

2.  문제

요약

• 수빈이는 현재 점 N에 있고, 동생은 점 K에 있습니다.
• 수빈이는 걷거나 순간이동을 할 수 있는데, 만약 수빈이의 위치가 X일 때, 걷는다면 1초 후에 X - 1 또는 X + 1로 이동하게 되고 순간이동을 하는 경우, 1초 후에 2 * X의 위치로 이동하게 됩니다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 그리고 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 100,000보다 작거나 같은 정수인 수빈이의 위치 N과 동생이 있는 위치 K가 주어집니다.
• 출력: 첫 번째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력하고 두 번째 줄에 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, K, min, count;
	static final int MAX_SIZE = 100001;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		K = scanner.nextInt();
		min = Integer.MAX_VALUE;
		count = 0;
	}
	
	static void solution() {
		min = Integer.MAX_VALUE;
		count = 0;
		bfs();
		sb.append(min).append('\n').append(count).append('\n');
		System.out.println(sb);
	}
	
	static void bfs() {
		int[] dist = new int[MAX_SIZE];
		Arrays.fill(dist, Integer.MAX_VALUE);
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(N);
		dist[N] = 0;
		while(!queue.isEmpty()) {
			int curPos = queue.poll();
			if(curPos == K) {
				if(min > dist[curPos]) {
					min = dist[curPos];
					count = 1;
				} else if(min == dist[curPos]) count++;
			}
			int next = curPos + 1;
			if(next < MAX_SIZE && dist[next] >= dist[curPos] + 1) {
				dist[next] = dist[curPos] + 1;
				queue.offer(next);
			}
			next = curPos * 2;
			if(next < MAX_SIZE && dist[next] >= dist[curPos] + 1) {
				dist[next] = dist[curPos] + 1;
				queue.offer(next);
			}
			next = curPos - 1;
			if(next >= 0 && dist[next] >= dist[curPos] + 1) {
				dist[next] = dist[curPos] + 1;
				queue.offer(next);
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}