[BOJ] 18352번_특정 거리의 도시 찾기_BFS (C++)

[문제]

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

도시 개수(N), 도로의 개수(M), 거리 정보(K), 출발 도시의 번호(X)를 입력받고 X에서 K만큼 떨어져있는 모든 도시를 출력하는 문제이다.

[사용 알고리즘]

BFS(너비 우선 탐색)

[풀이 핵심]

• 단방향 그래프를 입력받은 후 BFS를 통해 출발 지점으로 부터 다른 도시까지의 거리를 구해준다.
• BFS가 끝난 후 dist배열 안에 있는 값들 중 K와 같은 값이 정답이다. 그리고 check 변수를 통해 출발 지점으로 부터 K거리 떨어져있는 도시가 없을 경우도 확인해준다.

[코드]

//boj18352번_특정 거리의 도시 찾기_그래프

#include<iostream>
#include<queue>

using namespace std;

vector<int> graph[300001];
int dist[300001];
bool visited[300001];

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

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

		for (int i = 0; i < graph[V].size(); i++) {
			int num = graph[V][i];

			if (!visited[num]) {
				dist[num] = dist[V] + 1;
				visited[num] = true;
				q.push(num);
			}
		}
	}
}

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

	for (int i = 0; i < M; i++) {
		int V1, V2;
		cin >> V1 >> V2;

		graph[V1].push_back(V2);
	}

	BFS(X);

	bool check = false;

	for (int i = 1; i <= N; i++) {
		if (dist[i] == K) {
			check = true;
			cout << i << '\n';
		}
	}

	if (!check) {
		cout << -1;
	}

	return 0;
}