12851번: 숨바꼭질 2

문제

수빈이는 현재 점 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/12851

풀이 1: 방문 시간 배열을 이용한 중복 경로 허용 BFS

이 문제는 최단 시간만 구하는 것이 아니라, 동일한 최단 시간으로 도달하는 여러 가지 경로의 수를 함께 세어야 합니다.정수 배열에 도달 시간을 기록하여 중복 방문을 통제합니다.

1. 예외 처리 (N >= K): 수빈이의 위치 N이 동생의 위치 K보다 크거나 같다면, 수빈이가 할 수 있는 행동은 뒤로 걷기(X - 1)뿐입니다. 따라서 이 경우의 최단 시간은 N - K이며, 방법의 수는 무조건 1가지입니다.
2. 동일 시간 중복 방문 허용: 일반적인 BFS는 한 번 방문한 노드를 다시 큐에 넣지 않습니다. 하지만 이 문제에서는 방문 조건에 visited[nx] == visited[x] + 1을 추가하여, 이전에 방문했더라도 걸린 시간이 동일하다면 큐에 다시 넣어주어야 파생되는 모든 최단 경로를 누락 없이 셀 수 있습니다.
3. 도착점 카운팅: 큐에서 꺼낸 위치 x가 동생의 위치 K와 같다면 방법의 수(cnt)를 1 증가시킵니다. 이때 가장 먼저 K에 도달했을 때의 시간을 minTime에 저장해 두고, 큐에서 꺼낸 노드의 시간이 minTime을 초과한다면 더 이상 탐색할 필요가 없으므로 즉시 건너뜁니다(continue).

코드 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());

       // 1. 수빈이가 동생보다 앞서 있거나 같은 위치인 경우
       if (n >= k) {
          bw.write((n - k) + "\n1");
          bw.flush();
          return;
       }

       Queue<Integer> q = new LinkedList<>();
       int[] visited = new int[100001];
       
       q.add(n);
       visited[n] = 1; // 시간 계산을 편하게 하기 위해 1부터 시작 (출력 시 1을 뺌)

       int minTime = Integer.MAX_VALUE;
       int cnt = 0;

       while (!q.isEmpty()) {
          int x = q.poll();
          
          // 큐에서 꺼낸 위치의 도달 시간이 이미 찾은 최소 시간보다 크면 탐색 중지
          if (minTime < visited[x]) continue;

          // 동생을 찾은 경우
          if (x == k) {
             minTime = visited[x];
             cnt++;
             continue; // K에서 더 뻗어나갈 필요는 없으므로 continue
          }

          // 3가지 이동 방법 탐색
          for (int nx : new int[] {x - 1, x + 1, 2 * x}) {
             if (nx < 0 || nx > 100000)
                continue;
             
             // 핵심 로직: 처음 방문하거나, 같은 시간에 도달한 다른 경로인 경우 큐에 삽입
             if (visited[nx] == 0 || visited[nx] == visited[x] + 1) {
                visited[nx] = visited[x] + 1;
                q.add(nx);
             }
          }
       }

       bw.write((minTime - 1) + "\n" + cnt);

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

풀이 2: 지연 방문 처리를 이용한 Node 기반 BFS

두 번째 방식은 위치와 시간을 하나의 객체(Node)로 묶어 큐에 넣고, 큐에서 꺼낼 때 방문 처리를 하여 동일 시간에 유입되는 경로들을 큐에 담아내는 방식입니다.

1. 객체를 활용한 상태 저장: 위치(x)와 도달 시간(d)을 묶어서 관리하는 Node 객체를 만들어 큐에 넣습니다. 시간 배열 대신 불리언(boolean) 방문 배열을 사용해 메모리 활용을 변경합니다.
2. 지연 방문 처리: 큐에 다음 위치(nx)를 넣을 때는 방문 처리(true)를 하지 않고 확인만 합니다. 큐에서 원소를 꺼낼 때(q.poll()) 비로소 visited[node.x] = true를 수행합니다. 이렇게 하면 같은 시간(d)에 여러 경로가 같은 위치(nx)에 도달했을 때, 아직 그 위치가 방문 확정 전이므로 큐에 중복으로 삽입되어 경로가 유지됩니다. (단, 이 방식은 큐에 동일한 노드가 중복으로 많이 들어갈 수 있어 메모리 사용량이 다소 늘어납니다.)
3. 도착점 카운팅: 목적지 K에 처음 도달했을 때(cnt == 0), 그 시간을 d에 기록해 둡니다. 이후에 큐에서 꺼낸 노드가 목적지 K이면서 동시에 최초 도달 시간과 같다면(node.d == d), 방법의 수(cnt)를 계속해서 증가시킵니다.

코드 2

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());

       if (n >= k) {
          bw.write((n - k) + "\n1");
          bw.flush();
          return;
       }

       Queue<Node> q = new LinkedList<>();
       boolean[] visited = new boolean[200001];
       
       q.add(new Node(n, 0));
       visited[n] = true;

       int d = 0;   // 최단 시간 기록
       int cnt = 0; // 방법의 수 기록
       
       while (!q.isEmpty()) {
          Node node = q.poll();

          // 큐에서 꺼낼 때 방문 처리 (지연 방문)
          visited[node.x] = true;

          // 목적지에 도달한 경우
          if (cnt == 0 && node.x == k) {
             d = node.d;
             cnt++;
          } else if (node.d == d && node.x == k) {
             // 동일한 최단 시간으로 도착한 다른 경로
             cnt++;
          }

          for (int nx : new int[] {node.x - 1, node.x + 1, node.x * 2}) {
             // 큐에 넣을 시점에는 방문 처리(true)를 하지 않음
             if (nx < 0 || nx > 200000 || visited[nx])
                continue;
                
             q.add(new Node(nx, node.d + 1));
          }
       }

       bw.write(d + "\n" + cnt);

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

    // 위치와 시간을 함께 관리하는 클래스
    static class Node {
       int x, d;

       Node(int x, int d) {
          this.x = x;
          this.d = d;
       }
    }
}

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS)