본문 바로가기
Algorithm/Graph Search Algorithm

BOJ G4 13913 숨바꼭질4 JAVA

by rueMi 2024. 3. 22.

 

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net


문제 읽기

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

즉, 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]);
    }
}

'Algorithm > Graph Search Algorithm' 카테고리의 다른 글

BOJ G3 2206 벽 부수고 이동하기 JAVA  (0) 2024.04.09
BOJ G4 9019 DSLR JAVA  (0) 2024.03.27
BOJ S2 2805 나무 자르기 JAVA  (0) 2024.03.20
BOJ G4 9177 단어섞기 JAVA  (0) 2024.03.18
BOJ G4 12886 돌그룹 JAVA  (0) 2024.03.11