[백준] 12851번: 숨바꼭질 2 (Java)

1. 문제설명

수빈이가 점 N(0 ≤ N ≤ 100,000)에 있고, 동생이 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이가 X일 때 1초 후에 X-1 또는 X+1, 2*X의 위치로 이동할 수 있다.

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후이고, 가장 빠른 시간으로 찾는 방법의 수를 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

⇒ 최단 경로 구하기 → BFS

• 각 위치에 도달하는 시간을 `time` 배열에 저장 (최소 시간을 계산)
• BFS를 사용해 각 위치에서 이동 가능한 위치를 큐에 넣고 탐색한다.
• 방문한 위치에 도달한 시간을 저장한다. (`time` 배열에)
• 동생의 위치에 도달하게 되면
  • 이동 시간이 최소 시간인지 확인하고, 최소 시간을 갱신한다.
  • 이동 시간이 현재까지의 최소 시간과 같으면, 방법의 수(`count`)를 증가시킨다.

 

3. 틀린 이유

• 이동 가능한 위치를 탐색할 때, 방문하지 않은 위치만 고려했다.
  ⇒ 방문하지 않았거나 동일한 시간에 도달할 수 있는 위치를 모두 고려해야 한다.

 

4. 최종 코드

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

public class Main {
    static int n, k; // 수빈과 동생의 위치
    static int[] time = new int[100001]; // 위치에 대한 시간을 저장
    static int minTime = Integer.MAX_VALUE; // 최소 시간
    static int count = 0; // 방법의 수

    static void bfs(int s) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(s); // 시작 위치 큐에 추가

        while (!q.isEmpty()) {
            int cur = q.poll(); // 현재 위치를 꺼냄

            if(cur == k) { // 현재 위치가 동생의 위치일 경우
                if(time[cur] < minTime) { // 최소 시간인지 확인
                    minTime = time[cur]; // 최소 시간 갱신
                    count = 1; // count를 1로 초기화
                } else if(time[cur] == minTime) { // 동일한 최소 시간이 나오면
                    count++; // couht 증가
                }
            }

            int next[] = {cur-1, cur+1, cur*2}; // 이동할 수 있는 위치
            for(int i=0; i<3; i++) {
                // 다음 위치가 범위 내에 있는 경우
                if(next[i] >= 0 && next[i] <= 100000) {
                    // 방문하지 않은 위치이거나 동일한 시간에 도달할 수 있는 경우
                    if(time[next[i]] == 0 || time[next[i]] == time[cur] + 1) {
                        q.add(next[i]); // 다움 위치 큐에 추가
                        time[next[i]] = time[cur] + 1; // 다음 위치에 {현재까지의 시간 + 1}을 저장
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        bfs(n); // 수빈의 시작 위치로 bfs 호출
        System.out.println(minTime+"\\n"+count);
    }
}