BOJ : https://www.acmicpc.net/problem/1697
github : https://github.com/junho0956/Algorithm/blob/master/1697/1697/%EC%86%8C%EC%8A%A4.cpp
숨바꼭질 같은 경우의 문제는
DFS 보다는 BFS 를 통해서 문제를 해결하여야 합니다.
방문처리를 확인해주는 것은 필수이고, +1 -1 *2 의 순서를 어떻게 줘야할지 고민했는데
*2 같은 값의 변화가 큰 것 부터 주는 것이 맞다고 생각해서 아래와 같이 구현하였고
처음에 생각했던 것은 queue 로부터 가장 먼저 발견됬다고 해도
이게 가장 적은 횟수일 보장이 있을까 하는 생각에 저런식으로 구현하였는데
포스팅을 하면서 생각해보니 now == K 가 성립되는 것은
가장 먼저 발견된 것이니 애초에 나머지 큐에 있는 것이 현재 cnt 보다 적을수가 없다는게 성립되고,
continue 가 아니라 break; 를 해주시는게 시간상 빠를 것 같습니다.
|
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
|
#include <iostream>
#include <queue>
using namespace std;
int N, K;
queue<pair<int, int> > q;
bool visit[100001];
int main() {
cin >> N >> K;
int Min = 999999;
q.push({ N,0 });
while (!q.empty()) {
int now = q.front().first;
int cnt = q.front().second;
q.pop();
if (now > 100000 || now < 0) continue;
if (visit[now]) continue;
visit[now] = 1;
if (cnt >= Min) continue;
if (now == K) {
Min = cnt;
continue;
}
if (now != 0 && now < K) q.push({ now * 2, cnt + 1 });
q.push({ now + 1,cnt + 1 });
q.push({ now - 1,cnt + 1 });
}
cout << Min;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 13549번 숨바꼭질3 (0) | 2020.01.22 |
|---|---|
| BOJ 12851번 숨바꼭질2 (0) | 2020.01.22 |
| BOJ 10819번 차이를 최대로 (0) | 2020.01.22 |
| BOJ 2410번 2의 멱수의 합 (0) | 2020.01.22 |
| BOJ 1451번 직사각형으로 나누기 (0) | 2020.01.21 |
