알고리즘/BFS 문제풀이
[B5014] - 스타트링크
tongnamuu
2018. 8. 26. 20:57
https://www.acmicpc.net/problem/5014
이번에 풀 문제는 스타트링크입니다. 층 수가 있고 현재 위치에서 갈 수 있는 곳을 한 번씩 방문하며 갈 때마다 걸린시간을 dist배열에 저장합니다.
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 | #include <iostream> #include <queue> using namespace std; int dist[1000001] = { 0, }; int main() { int f, s, g, u, d; int upcnt = 0; int downcnt = 0; int ans = 0; queue<int>q; cin >> f >> s >> g >> u >> d;//f층 건물// 목적지 g //현재위치 s // 위로 u층씩 // 아래로 d층씩 q.push(s); dist[s] = 1; while (!q.empty()) { int pos = q.front(); q.pop(); int posup = pos + u; int posdown = pos - d; if (posup <= f && dist[posup] == 0) { dist[posup] = dist[pos] + 1; q.push(posup); } if (posdown >= 1 && dist[posdown] == 0) { dist[posdown] = dist[pos] + 1; q.push(posdown); } if (dist[g] != 0) break; } ans = dist[g] - 1; if (ans == -1) printf("use the stairs\n"); else printf("%d\n", ans); } | cs |