[Java] 백준 13549번: 숨바꼭질 3

[문제 바로 가기] - 숨바꼭질 3

💡 접근 방식

숨바꼭질 문제와 비슷하지만 다른 부분은 2*X 이동시에는 0초가 걸린다는 것이다.

따라서 1. BFS에서 2*X를 먼저 넣어주어야 함 2. 위치가 K일 경우 break 하면 안되고 최소값을 구해줘야 함
이 부분을 생각하지 못해 여러번 틀렸다 😅

풀이

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

public class Main {
	static int N, K, min = Integer.MAX_VALUE;
	static boolean visit[];
    
	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());
		
		visit = new boolean[100001];
		
		bfs();
		
		System.out.println(min);
	}
	
	public static void bfs() {
		Queue<int []> queue = new ArrayDeque<>();
		queue.add(new int[] {N, 0});
		visit[N] = true;
		
		while (!queue.isEmpty()) {
			int cur[] = queue.poll();
			int loc = cur[0];
			int count = cur[1];
			
			if (loc == K) min = Math.min(min, count);
			
			if (loc * 2 <= 100000 && !visit[loc * 2]) {
				queue.add(new int[] {loc * 2, count});
				visit[loc * 2] = true;
			}
			if (loc - 1 >= 0 && !visit[loc - 1]) {
				queue.add(new int [] {loc - 1, count + 1});
				visit[loc - 1] = true;
			}
			if (loc + 1 <= 100000 && !visit[loc + 1]) {
				queue.add(new int [] {loc + 1, count + 1});
				visit[loc + 1] = true;
			}
		}
	}
}