[백준] 13913 숨바꼭질 4 (JAVA)

문제 링크:

13913번: 숨바꼭질 4

 

 

난이도: 골드 4

 

 

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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초가 걸린다.

 

 

구현 방향:

이 문제는 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 minTime=Integer.MAX_VALUE;
    static boolean []visited=new boolean[100001];
    static int []prevPos=new int[100001];
    static List<Integer> resultList=new ArrayList<>();


    //bfs 방식으로 최적의 경로 탐색
    public static void solve(int pos){
        visited[pos]= true;
        Queue<int[]>q=new LinkedList<>();
        q.add(new int[]{pos,0});

        while (!q.isEmpty()){
            int[] arr = q.poll();
            int currPos=arr[0];
            int currTime=arr[1];

            //목적지일 경우
            if(currPos==K){
                minTime=currTime;
                resultList.add(K);
                break;
            }

            //+1 일 경우
            if(currPos<100000 &&!visited[currPos+1]){
                q.add(new int[]{currPos+1,currTime+1});
                prevPos[currPos+1]=currPos; //다음 경로에 대해 이전 경로 저장
                visited[currPos+1]=true;
            }

            //-1 일 경우
            if(currPos>0 &&!visited[currPos-1]){
                q.add(new int[]{currPos-1,currTime+1});
                prevPos[currPos-1]=currPos; //다음 경로에 대해 이전 경로 저장
                visited[currPos-1]=true;
            }

            //*2 일 경우
            if(currPos*2<=100000 &&!visited[currPos*2]){
                q.add(new int[]{currPos*2,currTime+1});
                prevPos[currPos*2]=currPos; //다음 경로에 대해 이전 경로 저장
                visited[currPos*2]=true;
            }
        }

    }

    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(prevPos,-1);
        //초기 세팅 끝

        //시작
        solve(N);

        //시간 출력
        System.out.println(minTime);

        //역순으로 저장되어있는 경로 reverse 해서 출력
        int index=K;
        while (true){
            if(index==N) break;
            resultList.add(prevPos[index]);
            index=prevPos[index];
        }

        Collections.reverse(resultList);
        for (int i=0; i<resultList.size(); i++){
            System.out.print(resultList.get(i));
            if(i!=resultList.size()-1) System.out.print(" ");
        }
    }
}

 

 

마무리하며:

이 문제는 ‘숨바꼭질 2’에서 활용한 BFS 구조에 경로 복원 과정을 추가한 변형 문제로, 핵심 아이디어만 이해하고 있다면 무리 없이 해결할 수 있었다. 보다 자세한 풀이 과정은 ‘숨바꼭질 2’ 관련 블로그 글에서 참고하면 된다.

 

 

감사합니다.