[BAEKJOON] - 1697번 : 숨바꼭질

1697번 문제 링크

📜 알고리즘 접근 방법

이 문제는 BFS 또는 DFS 알고리즘으로 접근이 가능합니다.

필자는 BFS로 구현하였습니다.

우선 1~100,000 가지의 수를 탐색하면서, k(동생의 위치)와 일치하면 값을 출력하도록 구현했습니다.]

주의할 점은 방문여부 체크를 boolean 여부로 설정할 필요 없이 탐색 범위와 동일한 크기의 배열에 depth 값을 비교하여 0인 경우, 탐색하도록 구현했습니다.

탐색은 현재 값보다 1 큰수, 1 작은 수, 2배의 수를 탐색하여 K와 같은지 여부를 확인하도록 구현해줍니다.

⚠️ 주의
탐색 범위 내에서만 탐색해줘야 하기 때문에 num의 값이 0보다 크거나 같읁지 또는 100,000만 보다 작거나 같은지 여부를 확인해줘야 합니다.

👾 구현

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

public class Main {
    static int[] count;
    static int n, k;

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

        String[] sArr = br.readLine().split(" ");
        n = Integer.parseInt(sArr[0]);
        k = Integer.parseInt(sArr[1]);

        count = new int[100_001];

        bfs(n);

        br.close();
    }

    static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(x);
        count[x] = 0; // depth 의미
        while (!q.isEmpty()) {
            int num = q.poll();

            if (num == k) {
                System.out.println(count[num]);
                return;
            }

            if (num - 1 >= 0 && count[num - 1] == 0) {
                count[num - 1] = count[num] + 1;
                q.offer(num - 1);
            }

            if (num + 1 <= 100_000 && count[num + 1] == 0) {
                count[num + 1] = count[num] + 1;
                q.offer(num + 1);
            }

            if (num * 2 <= 100_000 && count[num * 2] == 0) {
                count[num * 2] = count[num] + 1;
                q.offer(num * 2);
            }
        }
    }
}