BFS를 사용해 쉽게 풀 수 있는데,
현재 층에서 U, D를 해서 목적이 층이 나오면 이때 의 count를 출력해주면 된다. 목적지 층을 만나지 못하면 계단을 이용해야 한다.
주의 해야 할 부분은 방문체크를 해줘야 한다는 것. 각 층에서 U, D를 더한 층을 모두 방문하니 방문했던 층을 또 방문하는 것은 불필요한 일!
처음에 큐에서 꺼낸 층을 방문체크를 해주는 방식으로 했었는데 이렇게 하니 시간초과가 났다. 방문하기 전에 방문 체크를 미리 해줘야 한다. 아직도 왜 그런지는 잘 모르겠다.. 미리 방문체크를 하지 않으면 훨씬 더 많은 경우를 돌게되는 듯하다………
풀이보기
```c++
#include <iostream>
#include <queue>
int F, S, G, U, D;
int cnt[1000001];
bool visited[1000001];
int bfs() {
std::queue<int> q;
q.push(S);
visited[S] = true;
if(S < G && U == 0) return -1;
if(S > G && D == 0) return -1;
while (!q.empty()) {
int curr = q.front(); q.pop();
if(curr == G) return cnt[curr];
int n1 = curr + U;
int n2 = curr - D;
if(n1 <= F && !visited[n1]) {
cnt[n1] = cnt[curr] + 1;
visited[n1] = true;
q.push(n1);
}
if(n2 > 0 && !visited[n2]) {
cnt[n2] = cnt[curr] + 1;
visited[n2] = true;
q.push(n2);
}
}
return -1;
}
int main(int argc, const char * argv[]) {
scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
int ans = bfs();
ans == -1 ? printf("use the stairs\n") : printf("%d\n", ans);
return 0;
}
```
처음에는 현재 층이 목적지 층보다 작으면 U 크면 D를 해주는 방식으로 접근했었는데… BFS에 대한 이해가 전혀 없는 멍청하고 편협한 생각이었다…. 반성의 시간….