문제

예제 설명

입력

입출력 예시

코드

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

int N, M, S, E;
vector<vector<int>> city;

int bfs(int day) {
	if(day == S || day == E) return -1;
	vector<int> distance(N + 1, -1);
	vector<int> parent(N + 1, -1);
	queue<int> q;
	q.push(S);
	distance[S] = 1;
	parent[S] = 0;
	
	while(!q.empty()) {
		int here = q.front();
		q.pop();
		for(int i : city[here]) {
			if(i == day) continue;
			if(distance[i] == -1) {
				q.push(i);
				distance[i] = distance[here] + 1;
				parent[i] = here;
			}
		}
	}
	return distance[E];
}

int main() {
	cin >> N >> M >> S >> E;
	city = vector<vector<int>>(N + 1, vector<int>(0, 0));
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		city[a].emplace_back(b);
		city[b].emplace_back(a);
	}
	
	for(int i = 1; i <= N; i++) {
		cout << bfs(i) << "\n";
	}
	return 0;
}

bfs를 이용해서 최단 경로를 구하는 알고리즘을 이용했고, 기저 조건으로 공사하는 날과 시작 노드 or 끝 노드가 같으면 -1을 return하게 했다.
시작 노드부터 해당 노드까지의 거리를 distance 벡터에 저장하는데, 경로가 없는 경우 -1을 return해야 하므로 vector<int> distance(N + 1, -1) 로 초기화했다.
또한, 경로의 수가 아닌 지나가는 노드의 개수를 세야하므로 distance[S] = 1 로 초기화했다.