[Java] 숨바꼭질 - 1697

문제

난이도 - 실버1

유형 - BFS(너비 탐색)

문제링크

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

---

풀이

위 문제를 그래프로 그려봤을 때 아래 사진과 같았다.

엄청나게 쭉쭉 늘어나지만 이미 방문했던 곳은 가지 않기 때문에 정리하면 이렇게 된다.

왜 시작이 1초인지는 방문했던 배열과 방문하지 않았던 배열을 더 쉽게 구분하기 위함이다.
그래서 결과값을 리턴할 때 -1를 한 값을 리턴해준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, k;
    static int[] visited;   // 시간 저장 배열
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        visited = new int[100_001];     // 최대 넓이로 선언
        System.out.println(BFS(n));
        }
        private static int BFS(int n) {
        Queue<Integer> q = new LinkedList<>();
        visited[n] = 1;     // 맨 처음 방문했던 곳을 1초로 생각
        q.add(n);
        while (!q.isEmpty()) {      // 큐가 빌 때까지 반복
            int num = q.remove();
            if (num == k) {
                return visited[num] -1;     // 처음에 1초로 시작 했으므로 1초 빼주기
            }
            if (num -1 >= 0 && visited[num -1] == 0) {      // 지정된 수에서 1초 뺀 경우
                visited[num -1] = visited[num] + 1;
                q.add(num -1);
            } if (num + 1 <= 100_000 && visited[num + 1] == 0) {        // 지정된 수에서 1초 더한 경우
                visited[num + 1] = visited[num] + 1;
                q.add(num + 1);
            } if (num * 2 <= 100_000 && visited[num * 2] == 0) {        // 지정된 수에서 2를 곱한 경우
                visited[num * 2] = visited[num] + 1;
                q.add(num * 2);
            }
        }
        return -1;
        }
    }