[구름톤 챌린지] 대체 경로 (C++)

문제

N개의 도시와 M개의도로가 있다.

I일에는 i번 도시를 방문할 수 없다.

각 날짜별로 출발 도시부터 도착 도시까지의 경로에 포함되는 도시 개수 출력하기, 불가능한 경우에는 -1 출력

생각할 것

• 양방향 연결이므로 반대의 경우도 인접리스트에 추가해주었다.
• i일에는 큐에서 i번 도시를 꺼냈을 때 동작하지 않도록 조건을 추가하기
• 나머지는 그냥 날짜별로 BFS를 사용해서 최단 경로를 찾으면 된다.
  • visited배열에 방문한 도시 개수를 기록한 뒤, 도착지에 방문하면 해당 값을 결과배열에 기록한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	int N, M, S, E;
	cin >> N >> M >> S >> E;
	
	vector<vector<int>> adj(N + 1);

	int s, e;
	for(int i = 0; i < M; i++) {
		cin >> s >> e;
		adj[s].push_back(e);
		adj[e].push_back(s);
	}
	
	vector<int> res(N + 1, -1);
	for(int i = 1; i <= N; i++){ // 방문 날짜
		// 시작 위치 초기화
		queue<int> q; 
		vector<int> visited(N + 1);
		q.push(S);
		visited[S] = 1;
		
		// BFS
		while(!q.empty()){
			int cur = q.front();
			q.pop();
			if(cur == i) continue;
			if(cur == E){
				res[i] = visited[cur];
				break;
			}
			
			for(int j = 0; j < adj[cur].size(); j++) {
				int next = adj[cur][j];
				if(visited[next]) continue;
				q.push(next);
				visited[next] = visited[cur] + 1;
			}
		}
	}
	
	for(int i = 1; i <= N; i++) {
		cout << res[i] << endl;
	}
	
	return 0;
}