[백준] 13913번 - 숨바꼭질4

 

13913번: 숨바꼭질 4

 

 

이전에 풀이한 백준 1697번 숨바꼭질 문제에 조건이 하나 붙은 문제이다. 

[백준] 1697번 - 숨바꼭질

 

 

 

기존에는 동생을 찾는 가장 빠른 시간만을 출력하면 됐었는데, 이 문제에서는 동생을 가장 빠르게 찾는 시간과 더불어 동생에게까지 도달하는 경로까지 답으로 출력해야 한다.

 

 동생에게 도달하는 경로를 어떻게 저장할 수 있을지 고민해보았다. 큐에 담는 모든 과정에 대하여 배열이나 StringBuilder와 같은 객체를 생성해볼까 생각해보았지만 수빈이가 이동할 수 있는 점이 100,000개 이므로 메모리를 상당히 잡아먹을 것 같았다. 

그러다가 깨닳은 것이 최소시간을 구하는 논리를 그대로 적용하면 되는 것이었다.

 

1697번 숨바꼭질 문제에서 최소시간을 구하기위해 큐에서 현재 위치 n을 꺼내고 수빈이가 이동할 다음 위치를 큐에 넣기전 time[n-1], time[n+1], time[n*2]에 현재 위치에 도달하는데 걸리는 시간 + 1 을 해주었다.

 

이 원리를 거리에 적용하여 현재 위치에 도달하기 이전의 위치를 시간과 함께 저장한다면, 수빈이가 동생을 찾은 후 위치를 거슬러 올라가면 수빈이가 지나온 경로를 확인할 수 있을 것이다.

 

 

 

전체 코드

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

public class Main {
    
    static int MAX = 100000;
    static int MIN = 0;
    
    static int N, K;
    static int[][] time;
    static Queue<Integer> que;
    static Stack<Integer> stack;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        stack = new Stack<>();
        
        String[] input = br.readLine().split(" ");
        
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        
        time = new int[100001][2];
        
        
        
        sb.append(bfs(N) + "\n");
        
        
        // 수빈이가 지나온 경로를 역추적해야 하므로 스택에 저장하여 역으로 출력될 수 있도록 한다.
        int now = K;
        while (now != N) {
            stack.push(now);
            now = time[now][1];
        }
        
        stack.push(N);
        
        
        // 최종 출력
        while (!stack.isEmpty()) sb.append(stack.pop() + " ");
        
        System.out.println(sb);
        
        br.close();
    }
    
    static int bfs(int subin) {
        
        que = new LinkedList<>();
        
        time[subin][0] = 0;
        
        que.offer(subin);
        
        while (!que.isEmpty()) {
            
            int n = que.poll();
            
            if (n == K) break;
            
            int next = time[n][0] + 1;
            
            // time[N]배열의 index=0 에는 N까지 도달하는데 걸리는 최소시간이
            // time[N]배열의 index=1에는 N에 도달하기 이전의 위치가 저장된다. 
            if (n*2 <= MAX && time[n*2][0] == 0) {
                time[n*2][0] = next;
                time[n*2][1] = n;
                que.offer(n*2);
            }
            
            if (n-1 >= MIN && time[n-1][0] == 0) {
                time[n-1][0] = next;
                time[n-1][1] = n;
                que.offer(n-1);
            }
            
            if (n+1 <= MAX && time[n+1][0] == 0) {
                time[n+1][0] = next;
                time[n+1][1] = n;
                que.offer(n+1);
            }
        }
        
        return time[K][0];
    }
}