[백준 18232번] 텔레포트 정거장

[백준 18232번] 텔레포트 정거장

www.acmicpc.net/problem/18232

18232번: 텔레포트 정거장

 

 

 문제

 꽉꽉나라에 사는 주예와 방주는 점 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쌍이 없도록 주어진다.

 

 출력

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

 

 

 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int S, E;
vector<int> arr[300001];
bool visit[300001];

int bfs(int a){
	queue<pair<int, int>> q;
	visit[a] = true;
	q.push(make_pair(a, 0));
	
	while(!q.empty()){
		int a = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		if(a == E){
			return cnt;
		}
		
		if(a-1 > 0 && !visit[a - 1]){
			visit[a - 1] = true;
			q.push(make_pair(a-1, cnt+1));
		}
		
		if(a+1 <= N && !visit[a + 1]){
			visit[a + 1] = true;
			q.push(make_pair(a+1, cnt+1));
		}
		
		for(int i=0;i<arr[a].size();i++){
			int aa = arr[a][i];
			if(!visit[aa]){
				visit[aa] = true;
				q.push(make_pair(aa, cnt+1));
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> M;
	cin >> S >> E;
	for(int i=0;i<M;i++){
		int a, b; cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	
	cout << bfs(S);
	return 0;
}

 비슷한 문제가 있었던 것 같은데 기억이 안난다. 단순한 BFS문제로 범위 처리와 방문 처리만 잘 해주면 O(N+M)으로 쉽게 풀린다. 텔레포트 연결 정보에 대해서 양방으로 이동이 가능하다는 점만 체크해주면 틀릴 이유는 크게 없다.