[백준] 12851 숨바꼭질 2 (JAVA)

문제링크:

12851번: 숨바꼭질 2

 

 

난이도: 골드 ４

 

 

문제:

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

 

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

 

 

입력:

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

 

 

출력:

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

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

문제 이해:

이 문제는 간단히 말해 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생에게 도달하기 위한 최소 시간과 그 방법의 수를 구하는 것이다

 

이때 수빈이는 1초에 -1, +1, *2 만큼 이동할 수 있다

 

예제 입력 1을 보자. 시작 위치가 5이고 도착 위치가 17일 때 최단 경로는

5 → 10 → 9 → 18 → 17

5 → 4 → 8 → 16 → 17

이 두 가지가 있으며, 두 경우 모두 4초가 걸린다

 

 

구현방향:

작성자는 처음에 DFS를 사용하여 매 단계마다 세 가지 경우의 수를 탐색하고, 목적지에 도달했을 때의 시간을 리스트에 저장한 뒤 그중 최소 시간을 출력하였다. 그러나 재귀 호출의 특성상 불필요한 경로까지 모두 탐색하게 되어 시간 초과가 발생하였다.

 

이에 따라 BFS 방식으로 탐색을 변경하였다. BFS는 최단 경로 탐색에 적합하며, 탐색 과정에서 동일한 최소 시간이 여러 경로에서 나올 수 있기 때문에 단순한 visited 배열만으로는 처리가 어렵다. 따라서 각 위치에 도달하는 데 걸린 시간을 기록하고, 같은 시간에 도달한 경로를 모두 고려하여 최단 시간과 그 방법의 수를 구하도록 구현하였다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

시간초과 코드 (DFS):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, K;
    static int count = 0; // 최적으로 가능한 방법의 수
    static int minTime = Integer.MAX_VALUE;
    // 목적지로 도달 할 수 있는 시간을 담을 리스트
    static List<Integer> resultList = new ArrayList<>();

    public static void solve(int pos, int time) {
        // 가지치기: 범위 벗어나면 종료
        if (pos < 0 || pos > 100000) return;

        // 목적지인 경우
        if (pos == K) {
            if (time < minTime) {   // 더 짧은 시간 발견
                minTime = time;
                resultList.clear(); // 이전 기록 버리고 새로 저장
                resultList.add(time);
            } else if (time == minTime) { // 같은 최단 시간 추가
                resultList.add(time);
            }
            return;
        }

        if (time > minTime) return; // 현재 시간이 최소보다 크면 더 볼 필요 없음

        // 갈 수 있는 3가지 경우의 수
        solve(pos + 1, time + 1);
        solve(pos - 1, time + 1);
        solve(pos * 2, time + 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());

        // 탐색 시작
        solve(N, 0);

        // 최적 경로 개수 세기
        count = resultList.size();

        // 결과 출력
        System.out.println(minTime);
        System.out.println(count);
    }
}

 

정답코드(BFS):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, K;
    static int count = 0; // 최적으로 가능한 방법의 수
    static int[] dist = new int[100001];
    static int minTime=-1;


    public static void solve(int pos) {

        dist[N] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{pos,0});

        while (!q.isEmpty()){
            //현재 위치와 시간
            int[] arr = q.poll();
            int currPos=arr[0];
            int currTime=arr[1];

            // 이미 최단 시간보다 긴 경로는 무시
            if (minTime != -1 && currTime > minTime) break;


            //목적지면
            if (currPos == K) {
                if (minTime == -1) minTime = currTime; // 첫 발견
                if (currTime == minTime) count++;
            }

            //-1 일때
            if(currPos>0&& (dist[currPos-1]==-1 || dist[currPos - 1] == currTime + 1) ){
                dist[currPos-1]=dist[currPos]+1;
                q.offer(new int[]{currPos-1,currTime+1});
            }
            //+1 일떄
            if(currPos<100000 && (dist[currPos+1]==-1|| dist[currPos + 1] == currTime + 1) ){
                dist[currPos+1]=dist[currPos]+1;
                q.offer(new int[]{currPos+1,currTime+1});
            }
            //*2 일때
            if((currPos*2)<=100000 && (dist[currPos*2]==-1 || dist[currPos *2] == currTime + 1)){
                dist[currPos*2]=dist[currPos]+1;
                q.offer(new int[]{currPos*2,currTime+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());
        Arrays.fill(dist,-1);

        // 탐색 시작
        solve(N);


        // 결과 출력
        System.out.println(minTime);
        System.out.print(count);
    }
}

 

 

감사합니다.