[백준 5014][C++] 스타트 링크

간단하게 BFS로 풀리리라고 생각했는데 생각보다 많이 틀렸다.

내가 관과했던 점은 18번째 줄이다. S == G 인 경우, 그리고 U 나 D 가 0인 경우 18번째 줄이 없으면 오답이 된다.

 

또, 처음에는 int형 배열 graph의 값이 0일 경우를 아직 방문하지 않은 경우로 표현했는데 (bool형 visited 사용하지 않았다) 이 경우 역시 U 나 D 가 0 일 경우 문제가 된다. 

 

문제에서 나오는 범위를 유심히 확인해봤다면 틀리지 않을 수 있었던 문제 !!

 

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int graph[1000001];
bool visited[1000001];
 
queue<int> floors;
int main() {
    int F, S, G, U, D;
    cin >> F >> S >> G >> U >> D;
    memset(graph, 0, sizeof(graph));
    memset(visited, false, sizeof(visited));
 
    int ans = -1;
    floors.push(S);
    visited[S] = true;
    while (!floors.empty()) {
        int cur = floors.front();
        floors.pop();
        if (cur == G) {
            ans = graph[cur];
            break;
        }
        if (cur + U <= F && !visited[cur + U]) {
            graph[cur + U] = graph[cur] + 1;
            visited[cur + U] = true;
            floors.push(cur + U);
        }
        if (cur - D >= 1 && !visited[cur - D]) {
            graph[cur - D] = graph[cur] + 1;
            visited[cur - D] = true;
            floors.push(cur - D);
        }
   }
    if (ans == -1)
        cout << "use the stairs" << endl;
    else
        cout << ans << endl;
}