👀 문제
https://www.acmicpc.net/problem/1697
👊 도전
1. 설계
- 가장 빠른 시간을 구해야하므로 BFS를 사용한다.
- 총 세 가지 이동 방법으로 n에서 k까지 갈 수 있는 최단시간을 map에 저장한다.
- 중복 방문은 하지 않도록 한다.
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
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n,k;
static int[] map;
public static void bfs() {
Queue<Integer> q=new LinkedList<>();
q.offer(n);
map[n]=0;
int cnt=0;
while(!q.isEmpty()) {
int x=q.poll();
int[] dotX= {-1,1,x};
cnt=map[x]+1;
for(int i=0;i<3;i++) {
int xx=x+dotX[i];
if(0<=xx&&xx<=100000 && map[xx]==-1) {
map[xx]=cnt;
q.offer(xx);
if(xx==k) return;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
k=scan.nextInt();
map=new int[100001];
Arrays.fill(map, -1);
bfs();
System.out.println(map[k]);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- BFS를 사용한다
- 최소 시간을 구해야하므로 BFS를 사용한다.
- map을 -1로 초기화하여 방문하지 않았음을 표시한다. map[i]를 방문하면 i를 방문한 최소 시간을 저장한다.
- bfs()에서 시작점 n을 큐에 넣는다. n일 때는 0초이므로 map[n]=0으로 초기화하여 방문 표시를 한다.
- while문으로 큐를 탐색한다. 현재 위치 x에서 갈 수 있는 방법 세가지(-1, 1, x)를 선언한 후 새 위치 xx를 만들고, xx가 방문하지 않은 곳이라면 큐에 넣는다.
- xx는 이전에 방문하지 않은 곳이어야한다. 새 위치를 이전에 방문한 곳에 재방문하는 것은 이미 최소시간이 아닌 것이기 때문이다.
- 새 방문 지점 xx가 k라면 return으로 메소드를 종료하고, main()에서 출력한다.
👏 해결 완료!
- [BOJ] 백준 1697 - 숨바꼭질 (자바) https://zoonvivor.tistory.com/90