ALGORITHM/BOJ
[백준] 12851 숨바꼭질 2
0298
2021. 6. 27. 16:10
https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
2021-06-27
|
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
50
51
52
53
54
55
56
57
58
59
60
61
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main12851 {
public static int N, K;
public static int[] dir = {2, -1, 1};
public static boolean[] vtd;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
vtd = new boolean[100001];
Queue<Integer> q = new LinkedList<>();
q.add(N);
vtd[N] = true;
int time = 0;
int count = 0;
if(N == K) {
count = 1;
} else {
while(!q.isEmpty()) {
int size = q.size();
count = 0;
boolean flag = false;
while(size > 0) {
int x = q.poll();
vtd[x] = true;
int nx = 0;
for(int i = 0; i < dir.length; i++) {
if(i == 0) {
nx = x * dir[i];
} else {
nx = x + dir[i];
}
if(nx < 0 || nx > 100000) continue;
if(nx == K) {
flag = true;
count++;
}
if(!vtd[nx]) {
q.add(nx);
}
}
size--;
}
time++;
if(flag) break;
}
}
System.out.println(time);
System.out.println(count);
}
}
|
cs |
#문제풀이
몇 달만이지;;
보통의 bfs 문제를 풀때는 queue에 push 하기 전에 visit 체크를 했었다.
하지만 이 문제 같은 경우에는 push 할 때는 경우의 수가 겹칠 수가 있어서, pop 시점에서 visit 체크를 해줬어야 했다.
예시) 1 3 일 경우, 2 2 가 답으로 나와야한다.