5014 스타트링크

문제 링크

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

풀이

bfs처럼 생각해서 풀면 간단하다. 현재 칸, 현재칸에서 U, D로 갈 수 있는 칸들을 노드로 생각하면 bfs를 적용시킬 수 있다. 현재 칸의 depth는 이전 칸의 depth+1로 해주면서 bfs 알고리즘을 적용하고, bfs가 종료된 후 만약 G층의 depth가 0이라면(즉 G층에 도달하지 못해 depth가 업데이트 되지 않았다면) use the stairs를 출력하고 아니라면 depth를 출력해주면 된다.

C++ 코드

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

using namespace std;

int F, S, G, U, D;
bool visit[1000001];
int arr[1000001];

void bfs(int S){
    queue<int> q;
    q.push(S);
    visit[S] = true;
    
    while(!q.empty()){
    	int S = q.front();
    	if(S == G) return;
    	q.pop();
	    if(0<S-D && !visit[S-D]){
	    	q.push(S-D);
	    	arr[S-D] = arr[S]+1;
			visit[S-D] = true;
		}
	    if(S+U<=F && !visit[S+U]){
	    	q.push(S+U);
	    	arr[S+U] = arr[S]+1;
			visit[S+U] = true;
		}
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>F>>S>>G>>U>>D;
    
    if(S==G) {cout<<0<<endl; return 0;}
    
    bfs(S);
    
    if(arr[G] == 0) cout<<"use the stairs"<<endl;
    else cout<<arr[G]<<endl;
    
    return 0;
}