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

[문제]

5014번: 스타트링크 (acmicpc.net)

5014번: 스타트링크

[문제 풀이]

BFS를 이용해서 푸는 문제이지만 DFS에 기믹을 1개 추가해서 풀어볼려고 한다.

 

visited 배열을 이용해서 해당 지점에 왔을때 몇번이 걸렸는지 체크를 해주고 이미 방문했던 숫자보다 더 크다면 방문을 하지 말고 return을 해주자.

또한 현재 위치가 0이 되거나 f 보다 크다면 종료를 해주자.

그렇게 도착점에 도착했을때 가능한 방법중 가장 작은값을 출력하도록 하자.

 

자세한 부분은 코드를 보면서 파악하자.

[회고]

visited를 최소값으로 바꿔주는것을 안했다가 3번을 틀렸다. bfs가 아닌 dfs 방식을 이용했기에 이러한 부분에서 주의하도록 하자.

[코드]

#include <iostream>
#include <vector>

using namespace std;
int f,s,g,u,d;
int answer = 2100000000;
int visited[1000001];

void dfs(int now, int cnt){
    if(now <= 0 || now > f ){
        return;
    }
    if(now == s){
        answer = min(answer,cnt);
        return;
    }
    if(visited[now] > cnt){
        visited[now] = cnt;
        dfs(now - u, cnt + 1);
        dfs(now + d, cnt + 1);        
    }
    return;
}
    
int main(){
    cin>>f>>s>>g>>u>>d;

    for(int i = 0; i<=f; i++){
        visited[i] = 2100000000;
    }

    dfs(g,0);
    (answer == 2100000000) ? cout<<"use the stairs"<<endl : cout<<answer<<endl;
    return 0;
}