[BOJ 18232] 텔레포트 정거장 C++

난이도: Silver 2
번호: 18232
생성일: March 10, 2023 1:33 AM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

18232번: 텔레포트 정거장

C++

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N, M, S, E;
vector<vector<int>> map;
vector<bool> visit;

int BFS()
{
    queue<int> Q;
    Q.push(S);
    visit[S] = true;
    int depth = 0;

    while (!Q.empty())
    {
        int size = Q.size() + 1;

        while (--size)
        {
            int cur = Q.front();
            Q.pop();

            if (cur == E)
                return depth;

            for (int i : map[cur])
            {
                if (visit[i])
                    continue;

                Q.push(i);
                visit[i] = true;
            }
            if (cur > 1 && !visit[cur - 1])
            {
                Q.push(cur - 1);
                visit[cur - 1] = true;
            }
            if (cur + 1 <= N && !visit[cur + 1])
            {
                Q.push(cur + 1);
                visit[cur + 1] = true;
            }
        }
        ++depth;
    }
    return depth;
}

int main(void)
{
    scanf("%d %d %d %d", &N, &M, &S, &E);

    map.resize(N + 1);
    visit.resize(N + 1);

    for (int i = 0; i < M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }

    printf("%d", BFS());

    return (0);
}