BOJ 5014 · 스타트링크

알고리즘 분류 : BFS  

엘리베이터를 이용하여 S 층부터 G 층까지 가는 최단 거리를 구하는 문제다. 이동은 U 버튼, D 버튼을 통해서만 가능하다.

• 처음 층은 S 층부터 시작한다.
• 현재 층을 X 층이라 하면, 다음 층은 X+U 층이거나, X-D 층이다.
• 다음 층이 1 층에서 F 층 사이인지 확인한다.
• 존재하는 층이거나 아직 방문하지 않은 층이라면 이동한다.
• G 층에 도착할 때까지 BFS 탐색을 진행하고, 도착하면 버튼 누른 횟수를 출력한다.
• 도착하지 못하면, "use the stairs"를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int F, S, G, U, D;
int dist[1000001];

void bfs() {
    queue<int> q;
    q.push(S);
    dist[S] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == G) {
            printf("%d\n", dist[x]);
            return;
        }
        for (int nx : {x+U, x-D}) {
            if (nx < 1 || nx > F || dist[nx] >= 0) continue;
            q.push(nx);
            dist[nx] = dist[x]+1;
        }
    }
    printf("use the stairs\n");
}

int main() {
    scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
    memset(dist, -1, sizeof(dist));
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append(S)
    dist[S] = 0
    while q:
        x = q.popleft()
        if x == G:
            print(dist[x])
            return
        for nx in (x+U), (x-D):
            if 1 <= nx <= F and dist[nx] == -1:
                q.append(nx)
                dist[nx] = dist[x]+1
    print("use the stairs")

F, S, G, U, D = map(int, input().split())
dist = [-1]*(F+1)
bfs()

---

참고

• 백준 온라인 저지 : BOJ 5014