1697번: 숨바꼭질

문제 풀러가기

1697

설명

가장 빠른 시간, 즉 최단거리를 구하는 문제와 유사하므로 BFS로 푼다.

지나간 경로를 확인하기 위해 배열 visit을 만든다.

자세한 설명은 코드에 주석으로 달아놓았다.

코드

import java.util.*;

public class Main {
    static int n, k;
    static int[] visit = new int[100001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); // 수빈
        k = sc.nextInt(); // 동생

        bfs();
    }

    public static void bfs() {
        Queue<Integer> que = new LinkedList<Integer>();

        que.add(n); // 시작 위치 저장
        visit[n] = 1; // 시작 위치 체크

        while(!que.isEmpty()) {
            n = que.poll(); // 현재 위치 꺼냄

            if (n == k) break; // 동생과 위치가 같으면 종료

            //한 칸 앞으로 이동했을 때
            if(n + 1 <= 100000 && visit[n + 1] == 0) {
                que.add(n + 1); // 현재 위치 저장
                visit[n + 1] = visit[n] + 1; // 이동한 위치의 순서 저장
            }

            //한 칸 뒤로 이동했을 때
            if(n - 1 >= 0 && visit[n - 1] == 0) {
                que.add(n - 1);
                visit[n - 1] = visit[n] + 1;
            }

            //두 배 앞으로 이동했을 때
            if(n * 2 <= 100000 && visit[n * 2] == 0) {
                que.add(n * 2);
                visit[n * 2] = visit[n] + 1;
            }
        }

        System.out.println(visit[k] - 1); // 0이 아닌 1에서 시작하기 때문에 -1
    }
}