백준 5014번 문제 ( 스타트링크 )

문제 출처 : https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

이 문제는 현재 층에서 목적지 까지 갈 수 있는지 가지 못하는 지를 판별하는 문제이다.

그래서 BFS를 이용하여 방문 배열을 이용하여 가지 못하는 지를 판별하고

큐에 push, pop을 이용하여 답을 구할 수 있었다.

아래는 해당 문제를 풀이한 소스이다. 

#include<stdio.h>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
int F, S, G, U, D;
int flag = 0;
int visit[1000001];
struct list
{
    int cnt = 0;
    int floor;
};
queue <list> que;
void BFS()
{
    while (!que.empty())
    {
        list temp = que.front();
        que.pop();
        if (temp.floor == G)
        {
            flag = 1;
            printf("%d", temp.cnt);
            return;
        }
        for (int i = 0; i < 2; i++)
        {
            int nx, ny;
            if (i == 0)
            {
                nx = temp.floor + U;
                if (nx <= F && visit[nx]==0)
                {
                    visit[nx] = 1;
                    list A;
                    A.floor = nx;
                    A.cnt = temp.cnt + 1;
                    que.push(A);
                }
            }
            else if (i == 1)
            {
                nx = temp.floor - D;
                if (nx >= 1 && visit[nx] == 0)
                {
                    visit[nx] = 1;
                    list A;
                    A.floor = nx;
                    A.cnt = temp.cnt + 1;
                    que.push(A);
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
    list temp;
    temp.floor = S;
    que.push(temp);
    visit[S] = 1;
    // F 총 층수, S 지금 있는 층수, G 가야하는 충수, U 업, D 다운
    BFS();
    if (flag == 0)
        printf("use the stairs");
}