알고리즘
백준 1697 : 숨바꼭질
Aye Bye Eye
2020. 8. 10. 18:11
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가
www.acmicpc.net
|
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <algorithm>
#include <queue>
typedef int sec;
typedef int pos;
int N, K;
int minimumSec = 987654321;
int visited[200001];
struct state
{
int pos;
int sec;
};
void input()
{
std::cin >> N >> K;
}
void solve()
{
if (N == K)
{
minimumSec = 0;
return;
}
std::queue<state> bfs;
int dest = K;
bfs.push({ N, 0 });
while (bfs.empty() == false)
{
state curr = bfs.front();
visited[curr.pos] = 1;
bfs.pop();
if (curr.pos > dest)
{
int restSec = curr.sec + curr.pos - dest;
minimumSec = minimumSec > restSec ? restSec : minimumSec;
continue;
}
if (curr.sec > dest - N)
{
minimumSec = minimumSec > curr.sec ? curr.sec : minimumSec;
return;
}
if (dest == curr.pos * 2 || dest == curr.pos + 1 || dest == curr.pos - 1)
{
minimumSec = minimumSec > curr.sec + 1 ? curr.sec + 1 : minimumSec;
return;
}
else
{
if (visited[curr.pos * 2] == 0)
{
bfs.push({ curr.pos * 2, curr.sec + 1 });
}
if (visited[curr.pos + 1] == 0)
{
bfs.push({ curr.pos + 1, curr.sec + 1 });
}
if (curr.pos > 0)
{
if (visited[curr.pos - 1] == 0)
{
bfs.push({ curr.pos - 1, curr.sec + 1 });
}
}
}
}
}
void solve_dp()
{
}
void output()
{
std::cout << minimumSec;
}
int main()
{
input();
solve();
output();
return 0;
}
|
cs |
BFS의 뭐 개념이야 그렇다 쳐도
핵심은 이미 접근한 곳에 대해 어떻게 배제하는가
visited 변수를 안쓰고 하려면 어떤 방식이 필요할까...