백준 1697 자바 풀이

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

1697번: 숨바꼭질

BFS를 이용해 문제를 풀어보자.

처음엔 프로그래머스의 타겟넘버와 비슷한 문제인 줄 알고 DFS로 풀려고 하였으나, 가장 짧은 경로를 찾는 것이므로 각 뎁스를 따질 수 있는 BFS가 적절했다.

큐에 다음 숫자를 넣을 때 if 문에서 num + 1, num - 1, num * 2의 범위를 재줘야 한다. 그렇지 않으면 런타임에러가 날 수 있음!

처음엔 num + 1 <= check.length, num * 2 <= check.length 해도 상관이 없다고 생각했으나, 총 check 배열의 길이가 100,001 이므로 num이 100,000 이 들어갈 경우엔 check[100001]을 방문하게 되므로 IndexOutOfBound 오류가 난다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj1697 {

    static int N, K;
    static int[] check;

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        check = new int[100001];

        if (N == K) {
            System.out.println(0);
        } else BFS();

    }

    private static void BFS() {
        Queue<Integer> q = new LinkedList<>();
        int num;

        q.offer(N);

        while (!q.isEmpty()) {
            num = q.poll();

            if (num == K) {
                System.out.println(check[num]);
                return;
            }

            if(num + 1 < check.length && check[num + 1] == 0) {
                q.offer(num + 1);
                check[num + 1] = check[num] + 1;
            }
            if(num - 1 >= 0 && check[num - 1] == 0) {
                q.offer(num - 1);
                check[num - 1] = check[num] + 1;
            }
            if(num * 2 < check.length && check[num * 2] == 0) {
                q.offer(num * 2);
                check[num * 2] = check[num] + 1;
            }

        }
    }


}