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

문제: 스타트링크 (백준 5014번)

문제 분석

스타트링크라는 고층 건물에는 총 f층이 있고, 현재 s층에 있는 사람이 g층으로 가야 한다. 엘리베이터에는 위로 u층, 아래로 d층만 이동할 수 있는 버튼이 있다. 주어진 조건 내에서 최소한으로 버튼을 눌러 목표 층에 도착해야 한다. 만약 도착할 수 없다면 "use the stairs"를 출력해야 한다.

핵심 아이디어

1. BFS 큐 초기화
   현재 층(s)을 큐에 삽입하고, visited 벡터를 활용해 방문한 층과 해당 층까지의 버튼 누른 횟수를 기록했다.
2. 층 이동 로직
   큐에서 노드를 꺼낸 뒤:
   • 위로 이동: 현재 층 + u가 건물의 총 층수 f를 넘지 않으면서 방문한 적이 없다면 큐에 추가.
   • 아래로 이동: 현재 층 - d가 1층 이상이면서 방문한 적이 없다면 큐에 추가.
3. 종료 조건
   • 목표 층 g에 도착하면 버튼 누른 횟수를 출력하고 종료.
   • BFS가 끝나도 도착하지 못했다면 "use the stairs"를 출력.

전체 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int f, s, g, u, d; 
    cin >> f >> s >> g >> u >> d;

    queue<int> bfs;
    vector<int> visited(f + 1, -1);  // 방문 여부 및 누른 횟수 저장
    bfs.push(s);
    visited[s] = 0;  // 시작 층은 0회로 초기화

    while (!bfs.empty()) {
        int node = bfs.front();
        bfs.pop();
        if (node == g) break;  // 목표 층 도착 시 종료

        // 아래로 이동
        if (node - d > 0 && visited[node - d] == -1) {
            visited[node - d] = visited[node] + 1;
            bfs.push(node - d);
        }
        // 위로 이동
        if (node + u <= f && visited[node + u] == -1) {
            visited[node + u] = visited[node] + 1;
            bfs.push(node + u);
        }
    }

    // 결과 출력
    if (visited[g] == -1) 
        cout << "use the stairs";
    else 
        cout << visited[g];
}