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

5014번: 스타트링크

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

위로 U층, 아래로 D층 이동가능 할 때, S층에서 G층으로 가기 위해 눌러야하는 버튼 횟수의 최솟값을 구하여라. 

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은(이동할 때마다 1씩 추가) 최단거리 문제이므로 BFS로 접근할 수 있습니다. 탐색가능한 최대 노드의 수는 1,000,000이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다. 따라서 BFS를 통해 문제를 해결하겠습니다.

---

알고리즘 설계하기

 BFS 알고리즘은 일반적으로 다음과 같은 형태를 가집니다.

1. 큐에 시작위치를 넣고, 방문처리를 한다.
2. 큐가 빌 때까지 아래 동작을 반복한다.
 2.1 큐에서 가장 앞의 노드를 꺼낸다.
 2.2 현재 노드를 기준으로 이동 가능한 다음 노드를 탐색한다.
 2.2 다음 노드가 방문하지 않았다면 큐에 해당 노드를 추가하고, 방문처리를 한다. 

 

 일반적으로 방문처리는 방문처리 배열에 1과 같은 임의의 값을 넣어 처리하지만, 이 문제에서는 최단거리를 구하는 문제이므로 visited[다음 노드] = visited[현재 노드] + 1로 가중치를 1 더해 최단거리를 계산합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
using namespace std;

int f, s, g, u, d, visited[1000004];
queue<int> q;
int main(){
    cin >> f >> s >> g >> u >> d;
    visited[s] = 1;
    q.push(s); //시작 위치 방문처리 및 q에 push

    int y;
    while(!q.empty()){
        y = q.front(); q.pop();
        for(int dy : {u, -d}){ //다음 위치 계산
            int ny = y + dy;
            if(ny > f || ny < 1) continue; //다음 위치 범위 검사
            if(visited[ny]) continue; //방문한 경우
            visited[ny] = visited[y] + 1; //최단거리 갱신
            q.push(ny);
        }
    }
    if(visited[g]) //목표 위치에 도달한 경우
        cout << visited[g] - 1;
    else //목표 위치에 도달하지 못한 경우
        cout << "use the stairs";
    return 0;
}

 대부분의 코드가 일반적인 dfs와 동일하지만 다음 위치를 계산하는 부분에서 for(int dy : {u, -d})로 dy값을 가져오는 것을 볼 수 있습니다. 이와 같은 방식으로 구현하면 엘리베이터가 위로 가는 경우와 아래로 가는 경우를 나누지 않고 하나의 for문을 통해 해결할 수 있습니다.

 이때, 올라가는 경우는 현재위치에서 u만큼 추가되기 때문에 u값을 그대로 넣었고, 내려가는 경우는 현재위치에서 d만큼 감소하므로 -d로 작성하여 이후 ny를 계산하는 부분에서 같은 코드로도 계산할 수 있게 했습니다.

---