👀 문제
https://www.acmicpc.net/problem/13913
👊 도전
1. 설계
- 최소 시간을 구해야 하므로 BFS를 이용한다.
- time[i]를 이용하여 위치 i까지 걸린 시간을 저장하고, 중복 방문을 피한다.
- 이동 경로를 출력해야 하므로 prev[i]를 통해 i의 이전 위치를 저장한다. Stack을 이용하여 이동 경로를 출력한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int[] time=new int[100001]; // i 위치일 때 시간
int[] prev=new int[100001]; // i의 이전 위치
Arrays.fill(time, -1); // 초기화
Stack<Integer> st=new Stack<>();
Queue<Integer> q=new LinkedList<>();
q.offer(n); // 시작점
time[n]=0; // 시작 위치에서는 0초
while(!q.isEmpty()) {
int x=q.poll();
if(x==k) { // 도착
while(x!=n) { // k에서 n으로 다시 역이동
st.push(x);
x=prev[x];
}
st.push(n); // 마지막 시작점도 추가
break;
}
int[] dotX= {-1,1,x}; // 이동할 수 있는 경우의 수
for(int i=0;i<3;i++) {
int next=dotX[i]+x;
if(next<0 || next>100000 || time[next]!=-1) continue;
time[next]=time[x]+1; // 시간 계산
prev[next]=x; // next의 이전 위치(x) 저장
q.offer(next);
}
}
System.out.println(time[k]);
while(!st.isEmpty()) {
System.out.print(st.pop()+" ");
}
}
}
3. 결과
🤟 성공 🤟
4. 설명
- BFS를 이용한다
- 최소 시간을 구해야 하므로 BFS이다.
- time[]를 이용해 시간을 계산한다. -1로 초기화 한다. 이후 time[i]==-1이라면 아직 방문하지 않은 위치로 인식한다.
- prev[i]는 i의 이전 경로를 저장한다.
- 큐를 이용하여 k까지 이동한다
- 배열 dotX를 이용해 다음 노드로 갈 수 있는 경우를 만들고, for문을 통해 다음 위치를 계산한다(xx).
- xx의 범위가 0~100,000안에 들어오는지 확인한다. 이 범위를 초과하면 최소 시간이 될 확률이 낮다.
- xx가 방문하지 않은 노드인지 확인한다. 방문한 노드를 생각하지 않는다면, 같은 연산을 여러 번 수행하게 되므로 효율성이 떨어진다.
- 스택을 통해 경로를 출력한다
- k(==x)에서 부터 n까지 prev[]를 통해 역이동한다. 이때 이동 위치를 스택에 저장한 후, 마지막에 출력한다.
👏 해결 완료!
- [백준 13913: JAVA] 숨바꼭질 4 / DP, BFS, 역추적 https://dragon-h.tistory.com/37