BOJ G4 13913 숨바꼭질4 JAVA

13913번: 숨바꼭질 4

---

문제 읽기

해당 문제는 가장 빨리 갈 수 있는 시간, 그리고 그 때의 루트를 출력해야 한다. 이전에 가장 빨리 갈 수 있는 시간을 문제는 풀어봤던 기억이 있다. 하지만 이 문제는 루트까지 출력해야 한다!

즉, BFS + 루트 출력 문제라 볼 수 있다.

---

문제 풀기

BFS를 쓰는 이유는, 당연하겠지만 최소 시간을 구하기 때문이다. 이 문제는 완전 탐색을 해야 하는데, DFS, BFS 중에서 고르라면 최소 시간만 얻으면 되기 때문에 주저없이 BFS를 선택할 수 있다. DFS를 한다면 depth 끝까지 가기 때문에.. 쓸데없이 많이 탐색하게 된다.

그래서 일단 BFS로 구현을 했고, 최소 시간 구하는 건 문제가 없었다. 그 다음은 루트를 출력해야 한다. 처음에는 class Pos를 하나 만들고, 경로를 거기다 다 저장했더니 한 40퍼정도 가다가 시간 초과가 나왔다. 그래서 다른 방법을 생각하다가, 경로를 저장하는 배열을 하나 만들어서, 이전에 방문한 노드의 번호를 적어주는 방식을 선택했다.

이렇게 하면 최종 목적지에 도달했을 때, 최소 시간도 구하고, 또 최종 목적지부터 역탐색을 수행하여 경로를 출력할 수 있다.

코드를 보면 이해가 될 것이다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_13913_숨바꼭질4 {
    static class Pos{
        int no;
        int time;
        public Pos(int no, int time){
            this.no = no;
            this.time = time;
        }
    }
    static int M = 100001;
    static int[] preNode;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[M];
        visited[N] = true;

        Queue<Pos> q = new ArrayDeque<>();
        List<Integer> init = new ArrayList<>();
        init.add(N);
        q.offer(new Pos(N, 0));
        preNode = new int[M];
        preNode[N] = -1;
        while(!q.isEmpty()){
            Pos cur = q.poll();

            if (cur.no == K) {
                System.out.println(cur.time);
                findRoot(cur.no);
                break;
            }

						//이 부분은 반복되는 부분이기 때문에 메서드로 뺄 수도 있다.
            if (cur.no-1 >= 0 && cur.no-1 < M && !visited[cur.no-1]){
                visited[cur.no-1] = true;
                preNode[cur.no-1] = cur.no;
                q.offer(new Pos(cur.no-1, cur.time+1));
            }
            if (cur.no+1 >= 0 && cur.no+1 < M && !visited[cur.no+1]){
                visited[cur.no+1] = true;
                preNode[cur.no+1] = cur.no;
                q.offer(new Pos(cur.no+1, cur.time+1));
            }
            if (cur.no*2 >= 0 && cur.no*2 < M && !visited[cur.no*2]){
                visited[cur.no*2] = true;
                preNode[cur.no*2] = cur.no;
                q.offer(new Pos(cur.no*2, cur.time+1));
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = nodeLs.size()-1; i >= 0; i--){
            sb.append(nodeLs.get(i)).append(" ");
        }
        System.out.println(sb);
    }

    static List<Integer> nodeLs = new ArrayList<>();
    private static void findRoot(int no) { //경로를 역탐색하는 부분이다.
        if (no == -1) return;
        nodeLs.add(no);
        findRoot(preNode[no]);
    }
}