[Algorithm/Java] 백준 1697번 - 숨바꼭질

---

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

---

🔍 문제 풀이

문제 도식화

cur = 100000일 때 순간이동하면 200_000까지 갈 수 있으므로, 배열 크기를 200_001로 잡았다

💻 코드

전체 코드

문제를 정확히 파악하고, s, e처럼 내가 자주 쓰는 변수명으로 변환하여 접근하자!

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

public class Main {
    static int[] arr;
    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());

        arr = new int[200_001];

        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 미방문
                if(v[nx] == 0){
                    v[nx] = v[cur] + 1;
                    dq.offer(nx);
                }
            }
        }

        return 0;
    }
}

스켈레톤 코드

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

public class Main {
    static int[] arr;
    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());



    }

    static int bfs() {


    }
}