[백준 13913: JAVA] 숨바꼭질 4 / DP, BFS, 역추적

개요

 

숨바꼭질 시리즈에서 경로 탐색이 추가된 문제이다.

경로 탐색을 하기 위해서 찾은 경로의 부모 노드를 저장하여 풀이하였다.

동생의 위치에 도달한 경우는 동생의 위치부터 수빈이의 위치가 나올 때까지 loop를 돌며 경로를 탐색한다.

또한, 이때 경로를 stack에 저장하였는데 그 이유는 문제에서 수빈 -> 동생의 경로 순서대로 출력해야 하기 때문에

LIFO 구조가 필요했기 때문이다.

 

또한, BFS를 이용해서 최단거리를 탐색하였다.

 

문제

 

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

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

 

입력

풀이

 

1. 시작점을 큐에 추가하고, visited[시작점]을 1로 설정한다.

 

2. 반복문

      - 시퀀스

           - 1. 큐에서 조사하고 싶은 노드를 꺼낸다.

           - 2. 꺼낸 노드에서 -1, +1, *2 지점의 유효성을 검사한다.

                   - 유효한 경우 : 부모 노드의 정보를 저장하고, 큐에 추가한다.

      - 탈출조건 : visited[K] != 0 인 경우 동생의 위치에 도달했기 때문이다.

 

3. parent[]을 이용해서 수빈 -> 동생의 경로를 조사한다.

 

 

코드

 

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int INF = 100_000;
    private static int visited[];
    private static int parent[];

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 방문 여부와 동시에 최단거리를 저장하는 배열
        // 값이 0인 경우 미방문, 값이 0이 아니라면 방문을 의미한다.
        // 값이 0이 아닌 경우 최단거리의 값을 나타낸다.
        visited = new int[INF + 1];
        // 부모 노드를 저장하는 배열
        parent = new int[INF + 1];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        visited[N] = 1;

        // 후에 경로 탐색에 사용될 stack 자료구조
        Stack<Integer> path = new Stack<>();

        while(true){
            int cur = queue.poll();

            // 현재 위치 - 1이 아직 방문하지 않고
            // 유효한 범위인 경우
            if(checkLocation(cur - 1)){
                queue.add(cur - 1);
                visited[cur - 1] = visited[cur] + 1;
                // 부모노드 정보를 저장
                parent[cur - 1] = cur;
            }

            // 현재 위치 + 1이 아직 방문하지 않고
            // 유효한 범위인 경우
            if(checkLocation(cur + 1)){
                queue.add(cur + 1);
                visited[cur + 1] = visited[cur] + 1;
                // 부모노드 정보를 저장
                parent[cur + 1] = cur;
            }

            // 현재 위치 * 2이 아직 방문하지 않고
            // 유효한 범위인 경우
            if(checkLocation(cur * 2)){
                queue.add(cur * 2);
                visited[cur * 2] = visited[cur] + 1;
                // 부모노드 정보를 저장
                parent[cur * 2] = cur;
            }

            // 동생의 위치의 최단거리 값이 0이 아닌경우
            // 동생의 위치에 도달했다고 판단한다.
            if(visited[K] != 0) {
                int cur_idx = K;

                // 부모노드를 따라가며 경로를
                // 스택 자료구조에 저장한다
                while(cur_idx != N){
                    path.push(cur_idx);
                    cur_idx = parent[cur_idx];
                }
                // 시작 노드 추가
                path.push(cur_idx);
                break;
            }
        }

        // 시작점의 최단거리를 1로 지정했으므로
        // - 1 한 값을 결과로 출력한다(정확히는 출력 버퍼에 추가한다)
        bw.write(visited[K] - 1 + "\n");

        // 스택에서 빼며 경로를 출력한다
        while(!path.isEmpty()){
            bw.write(path.pop() + " ");
        }

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

    public static boolean checkLocation(int location){
        // 찾으려는 범위가 0 미만, 100_000 초과인 경우 false 반환
        if(location < 0 || location > INF) return false;
        // 이미 방문한 경우 false 반환
        if(visited[location] != 0) return false;

        return true;
    }
}