[백준] 18352 특정 거리의 도시 찾기

백준18452링크

1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1

입력

도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
(2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)
M개의 줄에 걸쳐서 두 개의 자연수 A, B - A에서 B로 이동하는 단방향 도로

출력

최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력

풀이

특정 출발점에서부터 다른 도시까지의 최단거리를 찾는 문제이기때문에 다익스트라로 풀이 가능
큐를 이용한 BFS로 풀이 -> 각 도시의 거리는 이전 도시까지의 거리 + 1

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

#define MAXN 300001
using namespace std;

int N, M, K, X; //도시의 수, 도로의 수, 목표거리, 출발도시 
vector<int> v[MAXN]; //그래프 저장
long dist[MAXN]; //거리 저장 
bool visited[MAXN]; //방문 저장
vector<int> result; //거리가 K인 도시 정보

void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	dist[start] = 0;

	while (!q.empty()) {
		int s = q.front();
		q.pop();

		for (int i = 0; i < v[s].size(); i++) {
			int next = v[s][i];

			if (!visited[next]) { //방문하지 않은 경우
				q.push(next);
				visited[next] = true;
				dist[next] = dist[s] + 1; //이전 도시까지의 거리 + 1

				if (dist[next] == K) { //거리가 K인 경우 result에 저장
					result.push_back(next);
				}
			}
		}

	}
	return;
}
int main() {
	cin >> N >> M >> K >> X;

	int a,b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
	}

	BFS(X);
	
	if (result.size() > 0) {
		sort(result.begin(), result.end()); //오름차순 정렬

		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << "\n";
		}
	}
	else {
		cout << -1;
	}
	return 0;
}