BOJ 문제풀이

BOJ 18232.cpp

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int N, M, S, E;
queue<pii> waiting;
vector<int> teleport[300001];
bool visited[300001];



int BFS(int x){
	waiting.push(pii(x,0));
	visited[x] = true;

	while(!waiting.empty()){
		pii now = waiting.front();
		int where = now.first;
		int cost = now.second;
		waiting.pop();
		if(where == E) return cost;

		if(where>1 && !visited[where-1]){
			waiting.push(pii(where-1,cost+1));
			visited[where-1] = true;
		}
		if(where<N && !visited[where+1]){
			waiting.push(pii(where+1, cost+1));
			visited[where+1] = true;
		}

		for (int i = 0; i < teleport[where].size(); ++i){
			if(!visited[teleport[where][i]]){
				waiting.push(pii(teleport[where][i],cost+1));
				visited[teleport[where][i]] = true;
			}
		}
	}

	return -1;
}



int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> N >> M >> S >> E;
for (int i = 0; i < M; ++i){
	int A, B;
	cin >> A >> B;
	teleport[A].push_back(B);
	teleport[B].push_back(A);
}


cout << BFS(S) << '\n';

return 0;
}