BOJ (C/C++) 18352번: 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

---

풀이

최단 거리 -> BFS 사용거리가 K인 도시를 찾았다면 오름차순 출력을 위해 우선순위 큐에 해당 도시를 삽입하고, 거리가 K 이상의 도시 정보는 필요하지 않으므로 큐에 삽입하지 않는다.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

vector <int> V[300001];
priority_queue <int, vector<int>, greater<int>> Print;

void BFS(int start, int K) {
	queue <pair<int, int>> Q;
	bool visited[300001] = { 0, };
	int now, dis;

	Q.push({ start,0 });
	visited[start] = true; 

	while (!Q.empty()) {
		// 현재 방문한 도시, 출발 도시 - 현재 도시 간 거리
		now = Q.front().first, dis = Q.front().second;
		Q.pop();
		
		if (dis == K) {
			Print.push(now);
			continue; // 거리가 K이상인 도시는 탐색할 필요가 없으므로
		}

		// 현재 도시와 인접한 도시들
		for (int i : V[now]) {
			if (!visited[i]) {
				Q.push({ i,dis + 1 });
				// 방문 표시
				visited[i] = true;
			}
		}
	}
}

int main() {
	int N, M, K, X, A, B;

	// input
	scanf("%d %d %d %d", &N, &M, &K, &X);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &A, &B);
		V[A].push_back(B);
	}

	// Find
	BFS(X, K);

	// print
	if (Print.empty()) printf("-1"); // 거리가 K인 도시가 없다면
	while (!Print.empty()) {
		printf("%d\n", Print.top());
		Print.pop();
	}

	return 0;
}