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

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

사고 과정

    - 시작층에서 시작하여 위 또는 아래로 움직인다.

        1. 위로 움직일 때, 최고 층을 넘게 되면 중단한다.

        2. 아래로 움직일 때, 1층 아래로 내려가면 중단한다.

        3. 같은 층을 오는 경우는 제외한다. 왜냐하면, 같은 곳에 오면 같은 과정을 똑같이 하기 때문에 순환이 이루어진다.

 

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int f, s, g, u, d;
int isVisited[1000001];
int answer = -1;
 
 
void bfs(){
    queue<pair<int, int> > q;
    q.push({s, 0});
    isVisited[s] = 1;
    
    while(!q.empty()){
        int here = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if(here == g){
            answer = cnt;
            return;
        }
        
        if(here + u <= f && !isVisited[here + u]){
            isVisited[here + u] = 1;
            q.push({here + u, cnt + 1});
        }
    
        if(here - d > 0 && !isVisited[here - d]){
            isVisited[here - d] = 1;
            q.push({here - d, cnt + 1});
        }
    }
}
 
int main(void){
    cin >> f >> s >> g >> u >> d;
 
    bfs();
    
    if(answer == -1) cout << "use the stairs";
    else cout << answer;
}

 

 

 

시행착오

    - DFS와 BFS의 확연한 차이를 알려주는 문제였다. DFS로 풀면 중간에 커트해준다고 해도 시간 초과가 발생했다. 문제의 의도는 최소 버튼 클릭 회수이기 때문에 굳이 깊게 탐색할 필요 없이 넓이부터 탐색하는 것이 빠르다. 본인은 이점을 지금까지 인지하지 못했다. 그러나 이번 문제로 문제의 의도에 따라 DFS 또는 BFS 써야 하는지 알 수 있었다. 

    - DFS

 

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int f, s, g, u, d;
int isVisited[1000001];
int answer = 987654321;
 
void dfs(int stair, int cnt){
    
    if(cnt >= answer) return;
     
    if(stair == g){
        answer = min(answer, cnt);
        return;
    }
    
    if(stair + u <= f && !isVisited[stair + u]){
        isVisited[stair + u] = 1;
        dfs(stair + u, cnt+1);
        isVisited[stair + u] = 0;
    }
    
    if(stair - d > 0 && !isVisited[stair - d]){
        isVisited[stair - d] = 1;
        dfs(stair - d, cnt+1);
        isVisited[stair - d] = 0;
    }
    
    
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(isVisited, 0, sizeof(isVisited));
    cin >> f >> s >> g >> u >> d;
    
    dfs(s, 0);
    if(answer == 987654321) cout << "use the stairs";
    else cout << answer;
 
}
 

 

 

 

 

    - 조건을 작성하는 부분이 본인은 애매했다. 문제에서 (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) 라는 부분은 엘리베이터가 이동 수행을 하지 못하고 다음 이동 명령을 수행할 수 있다고 이해했다. 본인만 그런가...?

    - 조건에서 제자리로 오는 경우를 떠올려야 했다. 제자리로 오게 되면 같은 과정을 반복할 것이기 때문에 순환이 발생한다. 따라서 isVisited로 체크해준다.

    - 정리 : 최소 이동 거리를 구하는 문제이므로 BFS 사용, 순환하는 것을 막기 위해서 제자리에 오는 것을 방지