백준 13549 - 숨바꼭질 3

문제 파악

수빈이가 동생의 위치를 찾을 수 있는 가장 빠른 시간을 찾는 문제
'가장 빠른 시간' -> BFS 사용
걸을 때는 가중치 1이 부여되고, 순간이동 할 때는 가중치 0이 부여된다.

0-1 BFS : 간선의 가중치가 0과 1로만 이루어져 있을 때 사용하는 알고리즘
1. 가중치 0 : 정점과 같은 레벨이다.
2. 가중치 1 : 정점보다 하나 아래 레벨이다.
-> 레벨이 최대 2가지로만 이루어져 있는 bfs

• 만약 같은 레벨이라면(가중치가 0이라면) 큐의 앞부분에 삽입
• 다음 레벨이라면(가중치가 1이라면) 큐의 뒷부분에 삽입 필요
  따라서 앞과 뒤에서 자유롭게 삽입, 삭제가 가능한 덱을 쓰는 것이 좋아보임
  

풀이

1. 스캐너를 사용해 수빈이의 위치 N과 동생의 위치 K를 입력받는다.
2. BFS를 수행할 덱과 최소시간을 저장할 배열을 생성한다.
3. 시작점으로 부터 시작한다.
   a. 시작점의 시간은 0으로 초기화
   b. 시작점을 덱에 넣는다.
4. BFS를 수행
   a. 덱이 빌 때까지
   b. 덱에서 현재 노드를 꺼내고
   c. 순간이동(가중치 0) 수행 : 현재 위치 * 2가 방문하지 않은 곳이라면 현재 위치를 업데이트 시키고 덱 앞에다 추가
   d. 뒤로 한 칸(가중치 1) 수행 : 현재 위치 - 1이 방문하지 않은 곳이라면 업데이트 후 덱 뒤에 추가
   e. 앞으로 한 칸(가중치 1) 수행 : 현재 위치 +1이 방문하지 않은 곳이라면 업데이트 후 덱 뒤에 추가
5. 최소시간 출력

코드

import java.util.*;

public class Main {
    static final int MAX = 100_001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int start = sc.nextInt();  // 수빈이 위치
        int target = sc.nextInt(); // 동생 위치

        int[] dist = new int[MAX];       // 최소 시간 저장 배열
        Arrays.fill(dist, -1);           // 방문하지 않은 위치는 -1
        Deque<Integer> deque = new ArrayDeque<>(); // 0-1 BFS를 위한 덱

        dist[start] = 0;      // 시작점 시간은 0
        deque.add(start);     // 시작 위치부터 탐색 시작

        while (!deque.isEmpty()) {
            int current = deque.poll(); // 현재 위치

            // 순간이동 (가중치 0)
            int teleport = current * 2;
            if (teleport < MAX && dist[teleport] == -1) {
                dist[teleport] = dist[current];
                deque.addFirst(teleport); // 0초이므로 덱 앞에 추가
            }

            // 뒤로 한 칸 (가중치 1)
            int back = current - 1;
            if (back >= 0 && dist[back] == -1) {
                dist[back] = dist[current] + 1;
                deque.addLast(back); // 1초이므로 덱 뒤에 추가
            }

            // 앞으로 한 칸 (가중치 1)
            int forward = current + 1;
            if (forward < MAX && dist[forward] == -1) {
                dist[forward] = dist[current] + 1;
                deque.addLast(forward); // 1초이므로 덱 뒤에 추가
            }
        }

        System.out.println(dist[target]); // 최소 시간 출력
    }
}