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 |