[C++] 백준 - 5014 : 스타트링크

문제 링크

5014번: 스타트링크

 

풀이 ) BFS

  버튼을 누르는 횟수를 표시하기 위해 pair를 사용할 수도 있지만 개인적으로 구분자로 사용하는 것이 편해서 구분자 '0'을 사용해서 구현했다.

 

  현재 있는 층과 구분자 0을 큐에 넣고 시작을 한다.

  반복문 안에서는 큐의 가장 앞 원소를 확인해서 먼저 도착했는지 확인한다.

  이후 구분자인지 확인하고 구분자 뒤에 원소가 없으면 즉 다음에 방문할 층이 없다면 반복문을 종료시키고 엘리베이터를 이용할 수 없기 때문에 ans = -1; break;를 해준다.

  원소가 있다면 아직 방문할 층이 남아있으므로 버튼을 누르는 횟수를 증가시키고, 큐에 구분자를 넣어준다.

 

  현재층에서 위로 올라갈 수 있으면 (n+u <= f) 다음에 방문할 층을 큐에 넣어준다. 방문 여부를 확인하지 않으면 중복이 발생할 수 있기 때문에 방문 여부도 확인하고, 방문 시 방문 여부를 고친다.

  아래로 갈 수 있으면 (n-d>0) 다음에 방문할 층의 방문 여부를 확인하고 큐에 넣어준다.

 

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

int f, s, g, u, d, ans;
int visited[1000001];
queue<int> q;
int bfs();

int main(void)
{
  scanf("%d%d%d%d%d", &f, &s, &g, &u, &d);

  visited[s] = 1;
  q.push(s);
  q.push(0);

  while(1){
    int n = q.front();

    if(n == g)
      break;
    if(n == 0){
      q.pop();
      if(q.empty()){
        ans = -1;
        break;
      }
      q.push(0);
      ans++;
      continue;
    }
    q.pop();

    if(n+u <= f && !visited[n+u]){
      visited[n+u] = 1;
      q.push(n+u);
    }
    if(n-d > 0 && !visited[n-d]){
      visited[n-d] = 1;
      q.push(n-d);
    }
  }

  if(ans != -1)
    printf("%d\n", ans);
  else
    printf("use the stairs\n");
  return 0;
}