[BOJ] 18232 : 텔레포트 정거장 - travelbeeee

문제 : https://www.acmicpc.net/problem/18232

---

[ 알고리즘풀이 ]

BFS 탐색을 이용해 현재 시점 S에서 시작해서 갈 수 있는 모든 지점을 밟아봅니다.

이때, 기존에 이미 밟았던 지점은 현재 밟아봐야 최소 시간이 아니므로 밟지 않았던 지점만 탐색을 진행해야 시간 초과, 메모리 초과 문제를 해결할 수 있다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int N, M, S, E, x, y;
vector<int> teleport[300001] = {};
queue<pair<int, int>> q;
bool visited[300001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M >> S >> E;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		teleport[x].push_back(y);
		teleport[y].push_back(x);
	}
	visited[S] = true;
	q.push(make_pair(S, 0));
	while (!q.empty()) {
		pair<int, int> s = q.front();
		q.pop();
		if (s.first == E) {
			cout << s.second;
			return 0;
		}
		for (int i = 0; i < teleport[s.first].size(); i++) {
			if (!visited[teleport[s.first][i]]){
				q.push(make_pair(teleport[s.first][i], s.second + 1));
				visited[teleport[s.first][i]] = true;
			}
		}
		if (s.first + 1 <= N && !visited[s.first + 1]){
			q.push(make_pair(s.first + 1, s.second + 1));
			visited[s.first + 1] = true;
		}
		if (s.first - 1 >= 1 && !visited[s.first - 1]){
			q.push(make_pair(s.first - 1, s.second + 1));
			visited[s.first - 1] = true;
		}
	}
}

---