[Beakjoon] 숨바꼭질 3 (C++)

문제 링크

BOJ 13549 : 숨바꼭질 3

문제

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

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

풀이

N에서 시작해서 K까지의 최단 소요 시간을 구하는 문제이다.
일반적인 BFS문제지만 순간이동이라는 요소가 특징인 문제이다.

우선순위 큐를 사용하기 위해 Loc라는 클래스를 정의했다.
compareTo 메서드를 오버라이드 해서 time을 기준으로 정렬되도록 했다.

각 반복문에서 현재 위치 X를 기준으로 이동할 수 있는 방향을 탐색한다.

• x*2 : x*2 가 100000을 넘어가지 않는 경우, 해당 위치까지 소요 시간이 현재 위치에서 가는 게 최적인 경우

• x+1 : x+1 이 100000을 넘어가지 않는 경우, 아해당 위치까지 소요 시간이 현재 위치에서 가는 게 최적인 경우

• x-1 : x-1 이 0보다 큰 경우, 해당 위치까지 소요 시간이 현재 위치에서 가는 게 최적인 경우

주의할 점

일반적인 bfs최단거리 문제라면 visited 배열을booleantype으로 지정하고 단순히 방문 여부만 체크해도 된다.

하지만 이 경우는 순간이동이라는 요소가 존재하기 때문에 방문 시 최단시간 여부를 확인해주고 방문해야한다.

예를 들어

4 6

입력이 주어졌을 때

최단 경로는 4 -> 3 -> 6 으로 소요시간은 1이다.

하지만 단순히 방문 여부만 체크하는 경우

첫번째 이동에서
4 -> 8 -> 7 (7까지 소요시간 1초)
가 발생하고, 7 -> 6 (소요시간 2초) 가 가능하다.

이때 6에 대한 방문 체크가 이루어지면 3 -> 6 을 시도하지 않게 되고 최소 소요시간이 2초로 오답이 나온다.

즉 순간이동이라는 요소로 인해서 같은 소요시간을 가진 위치에서 탐색을 시도하여 목적지에 도달할 때, 순간이동을 통해 도달하는 경우를 먼저 탐색해야하는데, 우선순위 큐만으로는 해당 순서를 조절할 수 없다.

따라서 visited배열에 도착 시간을 저장하고 해당 값을 비교함으로써 방문 여부를 결정해야한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class Loc implements Comparable<Loc> {
        int now;
        int time;

        Loc(int now, int time) {
            this.now = now;
            this.time = time;
        }

        @Override
        public int compareTo(Loc o) {
            return this.time - o.time;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N, K;
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        PriorityQueue<Loc> PQ = new PriorityQueue<>();
        int[] visited = new int[100001];
        Arrays.fill(visited, 987654321);
        PQ.add(new Loc(N, 0));
        visited[N] = 0;

        while (!PQ.isEmpty()) {
            Loc loc = PQ.poll();
            int x = loc.now;
            int time = loc.time;

            if (x == K) {
                System.out.println(time);
                return;
            }
            if (x * 2 <= 100000 && time < visited[x * 2]) {
                visited[x * 2] = time;
                PQ.add(new Loc(x * 2, time));
            }
            if (x + 1 <= 100000 && time + 1 < visited[x + 1]) {
                visited[x + 1] = time + 1;
                PQ.add(new Loc(x + 1, time + 1));
            }
            if (x - 1 >= 0 && time + 1 < visited[x - 1]) {
                visited[x - 1] = time + 1;
                PQ.add(new Loc(x - 1, time + 1));
            }

        }
    }

}