숨바꼭질


백준 [1697] 숨바꼭질

문제보기
Alt text

풀이방법

  • BFS

소스코드

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 int N, K, ans;
	static Queue<int[]> queue;
	static int[] v;

	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());
		ans = 987654321;
		queue = new LinkedList<>();
		v = new int[100001];

		queue.add(new int[] { N, 0 });
		v[N] = -1;
		if (N == K)
			ans = 0;
		else
			find();

		if (ans == 987654321)
			ans = -1;
		System.out.println(ans);
	};

	public static void find() {
		while (!queue.isEmpty()) {
			int[] q = queue.poll();
			if (ans <= q[1])
				continue;
			// 걷는경우
			int pre = q[0] - 1;
			if (pre == K) {
				ans = Math.min(ans, q[1] + 1);
				continue;
			} else if (pre >= 0) {
				if (v[pre] == 0 || v[pre] > q[1] + 1) {
					queue.add(new int[] { pre, q[1] + 1 });
					v[pre] = q[1] + 1;
				}

			}
			int next = q[0] + 1;
			if (next == K) {
				ans = Math.min(ans, q[1] + 1);
				continue;
			} else if (next <= 100000) {
				if (v[next] == 0 || v[next] > q[1] + 1) {
					queue.add(new int[] { next, q[1] + 1 });
					v[next] = q[1] + 1;
				}
			}
			// 순간이동 하는 경우
			int jump = 2 * q[0];
			if (jump == K) {
				ans = Math.min(ans, q[1] + 1);
				continue;
			} else if (jump >= 0 && jump <= 100000) {
				if (v[jump] == 0 || v[jump] > q[1] + 1) {
					queue.add(new int[] { jump, q[1] + 1 });
					v[jump] = q[1] + 1;
				}
			}
		}
	}
}