[백준] 5014번: 스타트링크 (C++)

www.acmicpc.net/problem/5014

5014번: 스타트링크

BFS를 이용해서 해결할 수 있었다.

 

+u와 -d씩 움직이며 탐색을 한다.

 

탈출 조건은 g(목표점)에 도달했을때 (vis배열 값 - 1) 을 return한다.

• vis배열은 버튼을 누른횟수가 들어가는데 처음에 0이 아닌 1이 들어가기때문에 (vis배열 값 - 1) 을 return 해준다.

탐색을 완전히 할때까지 g에 도달하지 못하면 "use the stairs"을 출력한다.

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

// f: 총 몇층?  1 ~ (1e6), s: 현재위치, g: 목표점
int f, s, g, u, d, result;
int vis[int(1e6) + 1];

int bfs(int cur) {
    queue<int> q;
    int dx[2] = {u, -d};

    vis[cur] = 1;
    q.push(cur);

    while (!q.empty()) {
        int x = q.front(); q.pop();
        
        if (x == g) {
            return vis[x] - 1;
        }

        for (int i = 0; i < 2; i++) {
            int nx = x + dx[i];

            if (nx < 1 || nx > f) continue;
            if (vis[nx]) continue;

            vis[nx] = vis[x] + 1;
            q.push(nx);
        }

    }
    return -1;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> f >> s >> g >> u >> d;

    result = bfs(s);

    if (result == -1) cout << "use the stairs";
    else cout << result;

    return 0;
}