[Algorithm/Java] 백준 13549번 - 숨바꼭질 3 (질문하기)

---

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

---

🔍 문제 풀이

문제 도식화

💻 코드

전체 코드

왜틀림?

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

public class Main {
    static int[] v;

    static int s, e;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        int ans = bfs();
        System.out.println(ans);

    }

    static int bfs() {
        // 1. 초기화
        Deque<Integer> dq = new ArrayDeque<>();
        v = new int[200_001];

        // 2. 초기값
        dq.offer(s);
        v[s] = 1;

        // 3. 탐색
        while(!dq.isEmpty()){
            int cur = dq.poll();
            // 3.1 종료조건
            if(cur == e){
                return v[e] - 1;
            }

            // 3.2 3방향, nx 범위
            int[] next = {cur + 1, cur - 1, cur * 2};
            for(int nx : next){
                if(nx < 0 || nx > 200_000) continue;

                // 3.3 미방문, 0-1 BFS
                if(v[nx] == 0){
                    if(nx == cur * 2){ // 순간이동 (가중치 0)
                        dq.offerFirst(nx);
                        v[nx] = v[cur];

                    }else{ // 걷기 (가중치 1)
                        dq.offerLast(nx);
                        v[nx] = v[cur] + 1;
                    }
                }
            }
        }

        return 0;
    }
}

스켈레톤 코드