[백준] 5014번: 스타트링크

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

1. 문제 풀이 방법

 

문제를 자세히 읽어보면, 1차원 BFS 문제임을 금방 알아차릴 수 있다. (... 눌러야 하는 버튼의 수의 최솟값 ...)

 

가장 버튼을 적게 누르면서 원하는 층으로 가기 위해서는 이미 들렸던 곳은 피해야 하는데, 이에 따라서

queue에 들려야(검사해야) 하는 층값을 push 해주는 조건은 최저층 ~ 최고층 사이이면서 한 번도 들리지 않았던 곳들

로 제한하면 된다.

 

또한 BFS의 종료조건은 강호가 G층에 도달했을 때이며, path 배열에 저장되어있는 버튼의 수를 출력하면 된다.

만약의 출발층에서 BFS를 돌려도 G층에 도달하지 못했을 경우에는 "use the stairs"라는 문자열을 출력하면 된다.

 

2. 소스 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int F, S, G, U, D;
const int MAX = 1000001;
int path[MAX];
bool visited[MAX];
vector<int> dx;
queue<int> q;

void BFS(int v) {
    visited[v] = true;
    q.push(v);

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

        for (int i = 0; i < 2; i++) {
            int nv = v + dx[i];

            if (0 < nv && nv <= F) {
                if (!visited[nv]) {
                    visited[nv] = true;
                    q.push(nv);
                    path[nv] = path[v] + 1;
                }
            }
        }
    }
}

int main() {
    cin >> F >> S >> G >> U >> D;

    dx.push_back(U);      // 위로 가는 버튼의 값
    dx.push_back(D * -1); // 아래로 가는 버튼의 값

    BFS(S);

    if (visited[G]) {
        cout << path[G];
    }
    else {
        cout << "use the stairs";
    }
}

 

제출 결과