[백준/Java] 1697 숨바꼭질

문제

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

풀이방법

1차원 bfs는 dx, dy를 미리 지정하지 못하니까 값이 바뀔 때 동적으로 계산할 수 있도록 !

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        final int MAX_VALUE = 100001;
        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());
        
        int[] dist = new int[MAX_VALUE];
        Arrays.fill(dist, -1);

        Queue<Integer> q = new ArrayDeque<>();
        q.offer(N);
        dist[N] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == K) {
                System.out.println(dist[cur]);
            }
            int[] next = {cur - 1, cur + 1, 2 * cur};
            for (int n : next) {
                if (n >= 0 && n < MAX_VALUE) {
                    if (dist[n] == -1) {
                        dist[n] = dist[cur] + 1;
                        q.offer(n);
                    }
                }
            }
        }
    }
}