백준 13549 숨바꼭질 3 (Java)

1. 문제 링크

13549번: 숨바꼭질 3

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. BFS를 이용해서 풀었다.
2. 시간이 0초 걸리는 *2 연산을 앞에 두고 +1, -1을 진행했다.

원래는 bfs로 풀리는 문제는 아닌데 *2 연산을 먼저 진행해서 풀린 것 같다.

약간 1의 위치에 있었을 때 *2를 먼저 해야 +1보다 먼저 방문하니까 시간이 덜 걸리기 때문에 무조건 *2를 앞에 둬야 한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		Queue<int[]> queue = new ArrayDeque<>();
		boolean[] visit = new boolean[100001];
		queue.offer(new int[] { N, 0 });
		visit[N] = true;
		int result = 0;
		out: 
		while (!queue.isEmpty()) {
			int[] temp = queue.poll();
			int where = temp[0];
			int num = temp[1];
			if (temp[0] == M) {
				result = num;
				break out;
			}

			if (where * 2 <= 100000 && !visit[where * 2]) {
				queue.offer(new int[] { where * 2, num });
				visit[where * 2] = true;
			}
			if (where - 1 >= 0 && !visit[where - 1]) {
				queue.offer(new int[] { where - 1, num + 1 });
				visit[where - 1] = true;
			}
			if (where + 1 <= 100000 && !visit[where + 1]) {
				queue.offer(new int[] { where + 1, num + 1 });
				visit[where + 1] = true;
			}

		}

		System.out.println(result);
	}
}