[백준] 1697번 숨바꼭질 - Java, 자바

난이도

실버 1

문제

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

풀이

그래프탐색 문제 가장 빠른 시간을 구해야하는 문제여서 BFS로 접근했다.

이 문제에서 헤맸던 점은 걸린 시간을 count로 코드로 짜다보니 결과가 너무 크게 나왔다.
시간을 어떻게 처리할지 고민을 하다가 1차원 배열에 저장하는 식으로 문제를 해결했다.
BFS문제에서 배열에 값을 저장하며 문제를 해결하는 경우가 많은데(ex. 토마토)
이 문제도 그렇게 접근하여 풀면 되겠다.

코드

package 그래프탐색;


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 BOJ1697 {
    static int n, k;
    static int[] arr;
    static Queue<Integer> q = new LinkedList<>();

    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());


        if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(bfs());
        }

    }

    static int bfs() {

        // 시간을 저장하는 배열선언
        arr = new int[100001];
        q.add(n);
        arr[n] = 1;
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int i = 0; i < 3; i++) {
                int nx;
                if (i == 0)
                    nx = x - 1;
                else if (i == 1)
                    nx = x + 1;
                else
                    nx = x * 2;

                if (nx == k)
                    return arr[x];

                if (nx >= 0 && nx < 100001 && arr[nx] == 0) {
                    arr[nx] = arr[x] + 1;
                    q.add(nx);
                }
            }
        }
        return 0;
    }

}