문제 : https://www.acmicpc.net/problem/5014
BFS를 사용해 쉽게 해결할 수 있습니다. 다만 if 문에서 visit 배열로 층의 방문 여부를 체크하기전에 배열의 index가 유효한 범위에 속해있는지 확인을 먼저해주어야 합니다.
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
| #include <iostream> #include <queue> #include <vector>
#define MAX_SIZE 1000001 using namespace std;
bool visit[MAX_SIZE]; int cnt[MAX_SIZE];
int main() { int f, s, g, u, d; cin >> f >> s >> g >> u >> d;
queue<int> q; visit[s] = true; cnt[s] = 0; q.push(s);
while(!q.empty()) { int now_floor = q.front(); int now_cnt = cnt[now_floor]; q.pop();
int next1 = now_floor + u; int next2 = now_floor - d;
if (next1 < MAX_SIZE && visit[next1] == false) { q.push(next1); visit[next1] = true; cnt[next1] = now_cnt + 1; }
if (next2 > 0 && visit[next2] == false) { q.push(next2); visit[next2] = true; cnt[next2] = now_cnt + 1; } }
if (visit[g] == true) { cout << cnt[g] << '\n'; } else { cout << "use the stairs" << '\n'; }
return 0; }
|