백준 18232 - 텔레포트 정거장(C++)

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

18232번: 텔레포트 정거장

BFS를 이용한 문제입니다.

현재 위치 S에서 출발해 E로 도착하려고 할 때, 걸리는 최소 시간을 구하는 문제입니다.

이동할 수 있는 방법은 +1 or -1 or 이어진 텔레포트를 이용해 움직일 수 있습니다.(움직일 때 걸리는 시간은 모두 1입니다.)

하나의 점에서 텔레포트가 여러개가 연결될 수도 있습니다. 따라서 배열이 아닌 vector를 이용해 연결된 텔레포트를 저장해줍니다.
(양방향이기 때문에 두 방향 모두 추가해줘야 합니다.)

3방법을 통해 이동하려는 다음 점을 찾았을 때,
+1 or -1인 경우는 이동하려는 범위가 1이상 N이하이며, 이전에 방문하지 않았어야 합니다.
텔레포트를 이용하는 경우에는 항상 범위 안이기에 이전에 방문했는지 여부만 확인합니다.

도착점에 도착했을 경우, 이동 시간을 출력해줍니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M, S, E;
int check[300001];
vector<int> port[300001];

int bfs(){
	queue<pair<int, int>> q;
	q.push({S, 0});
	check[S] = 1;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == E) return y;
		int x_1 = x + 1;
		int x_2 = x - 1;
		if(x_1 >= 1 && x_1 <= N){
			if(check[x_1] == 0){
				check[x_1] = 1;
				q.push({x_1, y+1});
			}
		}
		if(x_2 >= 1 && x_2 <= N){
			if(check[x_2] == 0){
				check[x_2] = 1;
				q.push({x_2, y+1});
			}
		}
		for(int i = 0; i < port[x].size(); i++){
			int xx = port[x][i];
			if(check[xx] == 0){
				check[xx] = 1;
				q.push({xx, y+1});
			}
		}
	}
}

void solve(){
	cout << bfs();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	cin >> S >> E;
	for(int i = 1; i <= M; i++){
		int x, y;
		cin >> x >> y;
		port[x].push_back(y);
		port[y].push_back(x);
	}	
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.