백준 스타트링크 C++

문제 링크 :https://www.acmicpc.net/problem/5014
문제 난이도: 골드 5
알고리즘 : bfs (너비 우선 탐색)
문제해결 아이디어: 시작층과 목표층이 주어지고 엘레베이터로 갈수 있는 UP 시 몇층을 한번에 올라갈 수 있는지 Down일때 몇층을 한번에 내려갈 수 있는지가 나온다.
시작층->목표층까지 갈수 있는 버튼수의 최솟값을 구하는 문제 이기 때문에 ->bfs로 풀었다.
UP으로 갈수 있는 값과 Down으로 갈수 있는 값을 벡터에 저장하고 인덱스 0 즉 가장 첫번째 값이 UP버튼으로 갈수 있는 값, 인덱스 1번이 Down버튼으로 갈수 있는 값으로 지정했다.
시작층을 bfs의 매개변수로 넣어 bfs함수가 실행되도록 작성했다.

<오류기록>

• 처음 실수한 부분: 처음에 문제를 제출했는데 메모리 초과가 발생했다.
  ->해결방법:vis즉 해당층에 방문했을경우 재 방문을 막아주는 배열이 필요하다.
  vis배열을 사용하지 않을경우, 같은층에 여러번 방문하는 경우가 발생해, 메모리 초과가 발생한다.

문제해결코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;

int f,s,g,u,d;
vector<int>dir;
int res=987654321;
int vis[1000001];
void bfs(int s){
//큐의 처음 값은 현재 층이고
//큐의 두번째 값은 해당층 까지 가기위해 버튼을 누른 횟수이다.
    queue<pair<int, int>>q;
    q.push({s,0});
    vis[s]=1;
    while(!q.empty()){
        int cur=q.front().first;
        int cnt=q.front().second;
        q.pop();
        if(cur==g){
            res=cnt;
            break;
        }
        if(dir[0]+cur<=f&&vis[dir[0]+cur]==0){
            q.push({dir[0]+cur,cnt+1});
            vis[dir[0]+cur]=1;
        }
        if(cur-dir[1]>=1&&vis[cur-dir[1]]==0){
            q.push({cur-dir[1],cnt+1});
            vis[cur-dir[1]]=1;
        }
        
       
        
        
        
        
    }
    
    
    
    
}


int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
  
   
    cin>>f>>s>>g>>u>>d;
    //맨 앞이 up값
    dir.push_back(u);
    dir.push_back(d);

    bfs(s);
    
    
    if(res!=987654321){
        cout<<res<<"\n";
    }else {
        cout<<"use the stairs"<<"\n";
    }
    
    
    
    
    
    return 0;
}