[Beakjoon] 백준 13549번 숨바꼭질3 (Java)

13549 숨바꼭질3

 

13549번: 숨바꼭질 3

 

난이도 및 유형

난이도 : 골드 5

유형 :  최단경로 / BFS / 다익스트라 / 0-1 BFS

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

문제풀이

숨바꼭질3 문제는 목표지점을 찾으면 탐색을 종료하는 일반적인 BFS로 풀이하기엔 적합하지 않다. BFS는 간선의 가중치가 모두 같아야 하기 때문이다. 하지만, 숨바꼭질3 문제는 가중치가 1 (+1, -1) 또는 0 (*2)으로 가중치가 다르다. 따라서, 숨바꼭질3 문제는 BFS를 사용해 탐색하되 목표지점에 도달한다고 탐색을 종료하면 안된다. Queue가 empty할 때까지 Queue에 들어있는 모든 노드를 탐색해 가중치를 확인하며 최소 가중치를 찾아야 한다.

 

최소 가중치를 찾기 위해서 방문배열(isVisited)을 boolean[]이 아니라 int[]를 사용했다. 해당 지점을 방문하는 최소 가중치를 비교하여 갱신해나가며 탐색했다. 만약, 현재 노드를 거쳐 다음 위치로 이동할 때 비용이 더 적은 경우라면 방문배열(isVisited)의 최소비용을 갱신하고 Queue에 다음 지점 노드를 추가하는 식으로 탐색을 진행했다.

 

해당 풀이의 시간복잡도는 O(V+E)로 하나의 Vertex에 3개의 Edge를 가정하면 V+E = V+3V = 4V = 4N 으로 N의 최대값 100,000을 대입하면 최대 400,000이다.

 

 

[정답코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    private static final int MAXIMUM_RANGE = 100_000;

    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        final int n = Integer.parseInt(stringTokenizer.nextToken());
        final int k = Integer.parseInt(stringTokenizer.nextToken());

        if (n == k) {
            System.out.println(0);
        } else {
            System.out.println(countTime(n, k));
        }
    }

    private static int countTime(final int n, final int k) {
        final Deque<Subin> queue = new ArrayDeque<>();
        queue.add(new Subin(n, 0));

        final int[] isVisited = new int[MAXIMUM_RANGE + 1];
        Arrays.fill(isVisited, MAXIMUM_RANGE);
        isVisited[n] = 0;

        while (!queue.isEmpty()) {
            final Subin current = queue.poll();

            final int nextA = current.location + 1;
            if (nextA >= 0 && nextA <= MAXIMUM_RANGE && current.time + 1 < isVisited[nextA]) {
                isVisited[nextA] = current.time + 1;
                queue.add(new Subin(nextA, current.time + 1));
            }

            final int nextB = current.location - 1;
            if (nextB >= 0 && nextB <= MAXIMUM_RANGE && current.time + 1 < isVisited[nextB]) {
                isVisited[nextB] = current.time + 1;
                queue.add(new Subin(nextB, current.time + 1));
            }

            final int nextC = current.location * 2;
            if (nextC >= 0 && nextC <= MAXIMUM_RANGE && current.time < isVisited[nextC]) {
                isVisited[nextC] = current.time;
                queue.add(new Subin(nextC, current.time));
            }
        }

        return isVisited[k];
    } // countTime

    static class Subin {
        private int location;
        private int time;

        public Subin(final int location, final int time) {
            this.location = location;
            this.time = time;
        }
    } // Subin

} // main