BOJ 1697. 숨바꼭질

BOJ 1697. 숨바꼭질

풀이

DP로 풀 수도 있지만 BFS로 문제를 풀어보았다.
1차원 배열에서 시작점에서 도착점 까지 걸리는 시간을 구하면 된다.

예를들어 시작점이 5라면,
먼저 5를 Queue에 넣고 5+1, 5-1, 5*2 를 계산하고,
해당칸은 방문한적이 없으니 visit에 거리 1을 저장한 후 5+1, 5-1, 5*2를 큐에 넣는다.

다음 큐에 존재하는 순서대로 6+1, 6-1, 6*2를 계산하고, 7은 방문한 적이 없으니 visit에 거리 2를 저장하고 큐에넣는다.
그 다음 5는 시작점으로 이미 방문한 적이 있으니 저장하지 않는다.
다음 12는 방문한 적이 없으니 visit에 거리 2를 저장하고 큐에 넣는다.

큐에 존재하는 순서대로 X+1, X-1, X*2를 계산하고 방문한 적이 있다면 Pass, 방문하지 않았다면 이전 거리 +1을 한 후 큐에 넣어준다.

수빈이가 존재 할 수 있는 위치는 0 ~ 100,000 이며 x2 를 할 경우에도 200,000이므로
BFS 탐색의 시간복잡도는 O(N)이니 주어진 시간 2초내에 충분히 탐색이 가능하다.
위 탐색을 완료한 뒤 동생이 있는 위치인 배열의 17번의 거리를 출력하면 된다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        final int MAX = 100002;

        Queue<Integer> queue = new LinkedList<>();
        int[] visit = new int[MAX];
        Arrays.fill(visit, -1);
        queue.offer(n);
        visit[n] = 0;

        while (!queue.isEmpty()) {
            int p = queue.poll();
            for (int i = 0; i < 3; i++) {
                int px = p;
                if (i == 0) px += 1;
                if (i == 1) px -= 1;
                if (i == 2) px *= 2;

                if (px < 0 || px >= MAX) continue;
                if (visit[px] != -1) continue;
                if (i == 0) queue.offer(p + 1);
                if (i == 1) queue.offer(p - 1);
                if (i == 2) queue.offer(p * 2);
                visit[px] = visit[p] + 1;
            }
        }
        System.out.println(visit[k]);
    }
}