[BaekJoon] #1697 - 숨바꼭질 [Java][C++]

문제 링크

---

1. 아이디어

수빈이가 동생을 찾을 수 있는 최단 시간을 찾는 문제로 3가지 이동 방법 모두 동일하게 1초가 소요되므로 최단 거리 BFS를 활용하면 간단하게 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(K)$	$O(K)$

($K$ = 값의 범위 $10^5 + 1$)

---

3. 코드

풀이 [Java][C++]

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

public class Main {

    static final int MAX = 100000;

    public static void main(String[] args) throws IOException {
        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());

        System.out.println(bfs(n, k));
    }

    static int bfs(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(n);

        boolean[] vis = new boolean[1 + MAX];
        vis[n] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                int cur = q.poll();
                if (cur == k) return dist;

                int nxt1 = cur - 1;
                if (nxt1 >= 0 && !vis[nxt1]) {
                    q.offer(nxt1);
                    vis[nxt1] = true;
                }

                int nxt2 = cur + 1;
                if (nxt2 <= MAX && !vis[nxt2]) {
                    q.offer(nxt2);
                    vis[nxt2] = true;
                }

                int nxt3 = cur * 2;
                if (nxt3 <= MAX && !vis[nxt3]) {
                    q.offer(nxt3);
                    vis[nxt3] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000;
bool vis[1 + MAX];

int bfs(int n, int k) {
    queue<int> q;
    q.push(n);

    vis[n] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int cur = q.front();
            q.pop();

            if (cur == k) return dist;

            for (int nxt : {cur - 1, cur + 1, cur * 2}) {
                if (0 <= nxt && nxt <= MAX && !vis[nxt]) {
                    q.push(nxt);
                    vis[nxt] = true;
                }
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    cout << bfs(n, k);
}

---