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

[문제]

 

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

[풀이]

 

S층에서  G층으로 가기 위해 눌러야 하는 버튼 수의 최솟값을 구하는 문제이다. 

 

BFS를 사용해 풀 수 있었다.

visited 배열을 사용해 이미 방문한 층이라면 넘어가고 

처음 방문한 층이라면 이전 층의 버튼 수 +1 을 저장한다.

이렇게 while문을 진행하다가 G 층을 만나면 버튼 수를 출력하고 BFS 함수를 return 한다.

 

 queue가 empty가 되어 while문이 끝나는 경우 엘레베이터로 이동할 수 없는 경우이므로 

"use the stairs"를 출력하고 BFS 함수를 return 한다.

 

 

[코드]

 

시간 : 8ms

 

 

#include <iostream>
#include <queue>
#define MAX 1000001

using namespace std;

/* S -> G , 못가면 use the stair 출력 */
int F,S,G,U,D;
int visited[MAX]={0,};
int dpos[2] = {0,};


void BFS(){

    queue <int> q;
    q.push(S);
    visited[S]=1;
    while(!q.empty()){
        
        int pos = q.front();
        q.pop();
        
        if(pos == G){
            cout << visited[pos]-1;
            return;
        }
        
        for(int i=0;i<2;i++){
            int npos = pos + dpos[i];
            
            if(npos < 1 || npos > F ||visited[npos]!=0)    continue;
            
            visited[npos] = visited[pos]+1;
            q.push(npos);
        }
    }
    
    cout << "use the stairs";
    return;

}

int main(void)
{
    cin >>F >> S >> G >> U >> D;
    dpos[0] = U;
    dpos[1] = -1*D;
    BFS();
    return 0;
}