[백준/13549] 숨바꼭질 3 - Java 자바

https://www.acmicpc.net/problem/13549

 

개념: 그래프 탐색, bfs, 다익스트라, ...

 

문제

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

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

 

입력

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

 

출력

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

 

---

 

풀이

전체코드

import java.util.*;

public class Main {
    static int N, K;
    static int max = 100000;
    static int[] time;

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

        N = sc.nextInt();
        K = sc.nextInt();
        time = new int[max + 1];
        Arrays.fill(time, Integer.MAX_VALUE);

        bfs();
        System.out.println(time[K]);
    }

    public static void bfs() {
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(N);
        time[N] = 0; // 시작점의 시간은 0

        while (!q.isEmpty()) {
            int current = q.poll();

            // 3가지 이동 방식 확인
            int[] nextPositions = {current * 2, current + 1, current - 1};
            for (int i = 0; i < 3; i++) {
                int next = nextPositions[i];

                if (next >= 0 && next <= max) {
                    if (i == 0) { // 순간이동 (0초)
                        if (time[next] > time[current]) {
                            time[next] = time[current];
                            q.offerFirst(next); // 순간이동은 우선 처리
                        }
                    } else { // 걷기 (+1초)
                        if (time[next] > time[current] + 1) {
                            time[next] = time[current] + 1;
                            q.offer(next); // 걷기는 뒤에 처리
                        }
                    }
                }
            }
        }
    }
}

 

 

bfs를 사용해서 풀었다. 

 

1. `boolean[] visited` 대신 `int[] time` 배열로 방문 여부와 최단 시간을 함께 관리한다.

• BFS 특성상 같은 노드를 여러 경로로 방문할 수 있다. 그러므로 `visited`는 단순히 방문했는지만 체크하고, 노드를 더 빠르게 방문할 가능성을 차단한다.
• `time[next] > time[current] + 비용` 조건을 통해 더 나은 경로가 있으면 갱신하고 재방문합니다.

 

2. `Deque` 를 사용한 이유?

• 양쪽에서 삽입과 삭제가 가능한 자료구조가 필요하다. 2*X 위치로 이동하는 작업이 우선순위가 높기 때문이다.
• `Deque`의 `offerFirst()` 메서드는 요소를 큐의 앞쪽에 삽입한다.

 

3. 귀찮다면 그냥 Node를 구현해서 time을 관리해도 된다. 메모리가 조금 더 소모된다.