(매일 BOJ) C++ 5014번 스타트링크

이번 문제는 5014번 스타트링크다

문제 요약

• 정점: 각 층 1..F
• 간선: x → x+U, x → x-D (범위 밖은 무시)
• 목표: 시작층 S에서 목표층 G까지 버튼 최소 횟수
• 불가능: 도달 못하면 "use the stairs"

접근법

이동 비용이 모두 동일(버튼 1회)하므로 무가중치 최단거리 => BFS가 정답이다
visited를 거리 배열로 사용해 -1(미방문), 0(시작), … 형태로 관리하면 오프바이원 실수를 예방할 수 있고, U==0 또는 D==0이라도 이미 방문한 층은 다시 넣지 않으므로 무한루프 없이 안전함

• 시간복잡도: 각 층을 최대 한 번 방문 → O(F)
• 공간복잡도: O(F)

알고리즘 설계

1. 입력으로 F, S, G, U, D를 받는다
2. 크기 F+1의 거리배열 visited를 -1로 초기화 후, 시작층 S를 0으로 설정해 큐에 푸시
3. 큐에서 층을 꺼내 두 이웃(+U, -D)을 확인: 범위 1..F이고 미방문이면 visited[next] = visited[cur] + 1로 기록하고 큐에 삽입
4. 탐색 중 G를 만나면 그때의 거리(버튼 횟수)를 반환
5. 큐가 빌 때까지 못 찾으면 "use the stairs"

작성코드

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


int F,S,G,U,D;
bool BFS (int & answer);
int main (void){
    cin >> F >> S >> G >> U >> D;
    int answer = 0;
    bool result = BFS(answer);

    if(result){
        cout << answer;
    }
    else{
        cout << "use the stairs";
    }

    return 0;
}

bool BFS (int & answer){
    vector<int> visited(F+1,-1);
    queue<int> q;
    q.push(S);
    visited[S] = 0;

    if(S == G) return true;

    while(!q.empty()){
        int current = q.front();
        q.pop();

        if(current == G) {
            answer = visited[G];
            return true;
        }

        for(int next : {current + U, current - D}){
            if(next > 0 && next <= F && visited[next] == -1){
                q.push(next);
                visited[next] = visited[current] + 1; 
            }
        }
    }
    return false;
}