백준 5014번 스타트링크 - C++(cpp) 풀이

---

 

1. 각 층을 그래프의 정점으로 생각한다.
2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다.
3. BFS를 사용해 S번 정점에서 시작해 G번 정점으로 가는 최단 거리를 구한다.

 

1. 각 층을 그래프의 정점으로 생각한다.

 최단거리 문제이므로 그래프로 바꾸어 생각해줄 것이다.

 

2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다.

 엘리베이터를 통해 이동할 수 있는 층은 방향 간선으로 연결해줄 것이다. 버튼을 1번 눌러 이동할 수 있으므로 가중치 1짜리 방향 간선으로 연결해준다. N층에서 N+U층으로 가는 방향 간선과 N-D층으로 가는 방향 간선을 추가해주면 된다. 이때 N+U와 N-D가 1이상 F이하여야 한다.

 

3. BFS를 사용해 S번 정점에서 시작해 G번 정점으로 가는 최단 거리를 구한다.

 이제 S번 정점에서 시작해 G번 정점으로 가는 최단 거리를 구하면 된다. 모든 간선의 가중치가 1이므로 BFS를 사용하면 쉽게 구현이 가능하다.

반응형

---

#include <iostream>
#include <queue>

using namespace std;

int F, S, G, U, D;
queue<int> q;
bool visit[1000001];
int dist[1000001];

int calc_min_dist() {
    visit[S] = true;
    q.push(S);
    
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        
        if (curr == G) return dist[G];
        
        int up = curr + U;
        int down = curr - D;
        
        if (up <= F && !visit[up]) {
            dist[up] = dist[curr] + 1;
            visit[up] = true;
            q.push(up);
        }
        
        if (down > 0 && !visit[down]) {
            dist[down] = dist[curr] + 1;
            visit[down] = true;
            q.push(down);
        }
    }
    
    return -1;
}

int main()
{
    cin >> F >> S >> G >> U >> D;
    
    int result = calc_min_dist();
    
    if (result == -1) cout << "use the stairs";
    else cout << result;
    
    return 0;
}