5014. 스타트링크

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

5014번: 스타트링크

 

Point

1. 옥상은 F층, 출발 층은 S층, S층에서 S+U층, S-D층으로 이동가능하다.

2. 이동할 때 마다 현재층 + 1을 저장해 준다. G층에 도달하면 BFS를 멈추면 된다.

 

 

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
using namespace std;

int f,s,g,u,d;
int visited[1000001];

bool bfs(int index)
{
    queue <int> q;
    q.push(index);
    while(!q.empty())
    {   
        int k = q.front(); 
        
        if(k==g)
        {   
            cout << visited[k]-1;
            return false;
        }
        
        if(k+u<=f)
        {   
            if(visited[k+u]==0)
            {
            q.push(k+u);
            visited[k+u] = visited[k] + 1;
            }
        }

        if(k-d>0)
        {
            if(visited[k-d]==0)
            {
            q.push(k-d);
            visited[k-d] = visited[k] + 1;
            }
        }
        q.pop();
    }
    
    return true;
}

int main()
{
    FASTio;
    cin >> f >> s >> g >> u >> d;

    visited[s]= 1;
    
    if(g==s) {
        cout << 0;
        return 0;
    }
    
    bool stare = bfs(s);
    
    if(stare)
    	cout << "use the stairs";
    

    return 0;
}

Solution

1. 우선 입력으로 받은 S층이 G층과 같은 경우 버튼을 누르지 않아도 되니 0을 출력하고 종료한다.

 

2. 그렇지 않은 경우 BFS를 진행하는데, 현재 층을 큐에 푸쉬하고 현재 층(S)에서 갈 수 있는 층인 S+U층, S-D층을 방문한 적이 없으면 

현재 층의 방문 횟수+1을 다음 층(S+U, S-D) 에 저장해주고  현재 층을 POP한다 

 

3. 이렇게 큐를 돌다가 G층에 도달하게 되면 visited[G]-1을 print 해주고 false를 리턴

 

4. 큐를 다돌렸는데도 G층에 도달하지 못한 경우 True가 반환되어 메인함수에서 use the stairs를 출력한다.

 

 

 

 

처음에 문제를 보고 분류가 BFS로 되어있길래, 이게 왜 BFS로 해결하는지 의아했다.

결국 최단경로를 찾는다는 측면에서 보면 BFS가 맞긴하지만, DP로도 해결할 수 있을 것 같았다. 하지만 아직 DP를 다루기에 서툴러서 우선 BFS로 풀어보았다. 나중에 DP를 공부하면 DP로 풀어봐야겠다.