5014 스타트링크

#include <stdio.h>
#include <queue>
#include <utility>
#include <vector>
 
using namespace std;
 
int f, s, g, u, d ;
 
int bfs() {
    vector<int> chk(1000005,0);
    queue<pair<int, int>> q;
 
    int cur = s;
    int cnt = 0;
    chk[cur] = 1;
    q.push(make_pair(cnt, cur));
 
    int flag = 0;
    while (!q.empty()) {
        cur = q.front().second;
        cnt = q.front().first;
    //    printf("cnt:%d, cur:%d\n", cnt, cur);
        q.pop();
 
        if (cur == g) {
            flag = 1;
            break;
        }
 
        // up
        int up = cur + u;
        if (up >= 1 && up <= f) {
            if (chk[up] == 0) {
                chk[up] = 1;
                q.push(make_pair(cnt + 1, up));
            }
        }
        // down
        int down = cur - d;
        if (down >= 1 || down <= f) {
            if (chk[down] == 0) {
                chk[down] = 1;
                q.push(make_pair(cnt + 1, down));
            }
        }
    }
    if (flag == 1)
        return cnt;
    else
        return -1;
}
 
int main() {    
    scanf("%d %d %d %d %d", &f, &s, &g, &u,&d);
    
    int rst = bfs();
    if (rst != -1)
        printf("%d", rst);
    else
        printf("use the stairs");
}

# 1.

항상 for문에다가 dx, dy 를 이용한 코드를 짜다보니 이번에도 습관적으로 continue 를 이용한 코드를 짰는데, 여기서 문제가 생겼다.

여기는 내부 for문이 따로 없기 때문에, continue 를 해버리면 queue에 관련된 while문 자체를 빠져나가버리기 때문에 틀리게 된다

주의하자!

# 2.

배열의 용량이 생각보다 적다는걸 알게됐다.

vector 를 사용하면 엄청난 용량의 배열을 사용할 수 있기 때문에, 애용하자!