13913번: 숨바꼭질 4

문제

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

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾는 가장 빠른 시간이 몇 초 후인지 그리고 그 이동 경로는 어떻게 되는지 구하는 문제입니다.

• 입력: 수빈이가 있는 위치 N과 동생이 있는 위치 K
• 출력:
  • 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력합니다.
  • 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분하여 출력합니다.

링크: https://www.acmicpc.net/problem/13913

풀이: 이전 방문 노드 기록(역추적)을 더한 BFS

최단 시간을 구하는 기존의 숨바꼭질 문제에서 경로 복원 개념이 추가된 문제입니다. BFS를 진행하면서 다음 위치로 넘어갈 때, '현재 위치'를 같이 기록해 두면 나중에 도착점에서부터 거꾸로 시작점까지 되짚어 갈 수 있습니다.

1. 상태 관리 배열:
   • visited 배열: 방문 여부와 동시에 걸린 시간을 기록합니다. (초기 시작점을 1로 두고 나중에 1을 빼서 계산의 편의를 도모합니다.)
   • prev 배열: 현재 위치에 도달하기 직전의 위치(부모 노드)를 기록합니다.
2. BFS 및 경로 기록:
   • 큐에서 꺼낸 위치 x가 목적지 k와 같다면 탐색을 종료합니다.
   • x - 1, x + 1, x * 2의 세 가지 이동 반경을 탐색합니다.
   • 범위를 벗어나지 않고 아직 방문하지 않은 곳(visited[nx] == 0)이라면 큐에 넣습니다.
   • 이때 visited[nx]에는 시간(visited[x] + 1)을 기록하고, prev[nx]에는 이전 위치인 x를 기록합니다.
3. 경로 역추적 (Path Reconstruction):
   • 탐색이 끝난 후 목적지 k부터 시작하여 prev 배열을 타고 역추적합니다.
   • 시작점의 prev 값은 처음에 -1로 설정해 두었으므로, x != -1인 동안 계속해서 리스트에 담아줍니다.
   • 역추적으로 담은 경로는 '목적지 -> 시작점' 순서이므로, 출력할 때는 리스트의 맨 뒤에서부터 역순으로 출력하여 '시작점 -> 목적지'의 올바른 경로를 만들어냅니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int k = Integer.parseInt(st.nextToken());

       Queue<Integer> q = new LinkedList<>();
       
       // 최대 100,000에서 *2 이동을 고려하여 넉넉하게 200,001로 배열 크기 설정
       int[] visited = new int[200001];
       int[] prev = new int[200001];
       
       // 1. 시작점 초기화
       q.add(n);
       visited[n] = 1; // 시간 기록용 (0은 미방문과 겹치므로 1부터 시작)
       prev[n] = -1;   // 역추적의 종료 지점을 표시하기 위해 -1 사용

       // 2. BFS 탐색
       while (!q.isEmpty()) {
          int x = q.poll();
          
          // 목적지 도달 시 탐색 종료
          if (x == k) {
             break;
          }

          // 3가지 이동 경로 확인
          for (int nx : new int[] {x - 1, x + 1, x * 2}) {
             // 맵을 벗어나거나 이미 방문한 곳이라면 무시
             if (nx < 0 || nx > 200000 || visited[nx] != 0)
                continue;
             
             q.add(nx);
             visited[nx] = visited[x] + 1;
             
             // [핵심] 다음 위치로 가기 위해 현재 위치를 기록
             prev[nx] = x;
          }
       }

       // 3. 최단 시간 출력 (시작을 1로 했으므로 1을 차감)
       bw.write((visited[k] - 1) + "\n");
       
       // 4. 경로 역추적
       List<Integer> list = new ArrayList<>();
       // k에서 시작하여 이전 노드를 계속 따라가며 -1(시작점)이 나올 때까지 반복
       for (int x = k; x != -1; x = prev[x]) {
          list.add(x);
       }

       // 역추적된 경로는 목적지->시작점 순이므로, 뒤에서부터 거꾸로 출력
       for (int i = list.size() - 1; i >= 0; i--) {
          bw.write(list.get(i) + " ");
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS), 최단 경로 역추적