백준 5014번 스타트링크

문제 링크입니다: https://www.acmicpc.net/problem/5014

BFS(Breadth First Search) 알고리즘을 적용하여 푸는 문제였습니다.

기존의 BFS 문제와는 달리 Dir 구조체와 Dir 배열을 미리 정의하지 않고 while문 내에서 다음 층(위로 갔을 경우, 아래로 갔을 경우) 두 가지만 고려해주면 되는 문제였습니다.

결과는 백준 2589번 보물섬(http://jaimemin.tistory.com/644) 문제와 같이 cache[도달한 층] - 1을 출력해야합니다.

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int F, S, G, U, D;

int cache[MAX];

 

int BFS(void)

{

        queue<int> q;

        q.push(S);

        cache[S] = 1;

 

        while (!q.empty())

        {

                 int curFloor = q.front();

                 q.pop();

 

                 //목표층에 도달하면

                 if (curFloor == G)

                         return cache[curFloor] - 1;

 

                 //위로 U층, 아래로 D층 갈 수 있다

                 int nextFloor[2] = { curFloor + U, curFloor - D };

                 for(int i=0; i<2; i++)

                         //범위 내에 있고 이미 도달한 층이 아닐 경우에만 update

                         if (1 <= nextFloor[i] && nextFloor[i] <= F && cache[nextFloor[i]]==0)

                         {

                                 cache[nextFloor[i]] = cache[curFloor] + 1;

                                 q.push(nextFloor[i]);

                         }

        }

        return -1; //목표층에 도달하지 못하면

}

 

int main(void)

{

        cin >> F >> S >> G >> U >> D;

 

        int result = BFS();

        if (result == -1)

                 cout << "use the stairs" << endl;

        else

                 cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~