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

 

 

문제

꽉꽉나라에 사는 주예와 방주는 점 S에서 만나 저녁을 먹기로 했다. 주예는 점 S에 도착했지만 길치인 방주가 약속시간이 30분이 지나도 나타나지 않자 방주에게 연락을 하여 방주가 점 E에 있다는 사실을 알아냈다. 주예는 방주에게 그 위치에 가만히 있으라고 했고, 직접 점 E로 가려고 한다.

꽉꽉나라에는 1부터 N까지의 각 점에 하나의 텔레포트 정거장이 위치해 있고 텔레포트를 통하여 연결되어 있는 다른 텔레포트의 정거장으로 이동할 수 있다. 주예는 현재 위치가 점 X라면 X+1이나 X-1로 이동하거나 X에 위치한 텔레포트와 연결된 지점으로 이동할 수 있으며 각 행동에는 1초가 소요된다. 배가 고픈 주예는 최대한 빨리 방주와 만나고 싶어 한다.

N과 텔레포트 연결 정보가 주어질 때 점 S에 있는 주예가 점 E까지 가는 최소 시간을 구해보자.

입력

첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000))

두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E)

그 다음 줄부터 M개의 줄에 걸쳐 텔레포트 연결 정보를 의미하는 정수 x, y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

x y는 점 x의 텔레포트와 점 y의 텔레포트가 연결되어 있다는 뜻이다. M개의 연결정보는 중복되는 x y쌍이 없도록 주어진다.

출력

첫 번째 줄에 주예와 방주가 만날 수 있는 최소 시간을 출력한다.

 

 

접근 방식

 

최단 거리를 구하는 간단한 BFS다.

이때 주의할 것은 텔레포트에 연결이 되어 있다면 x+1, x-1로 이동하는것 외에 텔레포트로도 이동해야한다!!

또한, 텔레포트는 양방향으로 이동이 가능하다. 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int visited[300003];

int main() {
    int N,M; cin>>N>>M;
    int S,E; cin>>S>>E;
    vector<vector<int>> path(N+1);

    for(int i=0; i<M; i++) {
        int a,b; cin>>a>>b;
        path[a].push_back(b);
        path[b].push_back(a);
    }

    if(S == E) {
        cout<<0;
        return 0;
    }

    queue<int> q;
    memset(visited, -1, sizeof(visited));

    q.push(S);
    visited[S] = 0;

    while (!q.empty())
    {
        int x = q.front(); q.pop();
        if(x == E) break;

        if(!path[x].empty()) {
            for(auto c: path[x]) {
                if(visited[c] != -1) continue;
                q.push(c);
                visited[c] = visited[x] + 1;
            }
        }


        for(auto nxt : {x+1, x-1}) {
            if(nxt > N || nxt < 1 || visited[nxt] != -1) continue;
            q.push(nxt);
            visited[nxt] = visited[x] + 1;
        }
    }
    cout<<visited[E];
}