[BOJ/C++] 18352 특정 거리의 도시 찾기

BFS를 이용해 문제를 해결할 수 있습니다.

1. 시작 노드부터 모든 노드를 방문하며 거리를 업데이트 합니다.
2. 방문 배열에서 K 거리를 만족하는 노드가 있다면 출력하고
3. 만족하는 노드가 한 개도 없다면 -1을 출력합니다.

// boj s2 18352
// 특정 거리의 도시 찾기
#include<iostream>
#include<algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>

using namespace std;

void BFS(int node);
static vector<vector<int>> A;
static vector<int> visited;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M, K, X;
	cin >> N >> M >> K >> X;
	A.resize(N + 1);

	for(int i=0; i<M; i++)
	{
		int S, E;
		cin >> S >> E;
		A[S].push_back(E);
	}

	visited.resize(N + 1);

	for (int i = 0; i <= N; i++)
		visited[i] = -1;

	BFS(X);

	bool flag=false;
	for(int i=0; i<=N; i++)
	{
		if (visited[i] == K)
		{
			cout << i << '\n';
			flag = true;
		}
	}
	if (!flag)
		cout << -1;

	return 0;
}

void BFS(int node)
{
	queue<int> q;
	q.push(node);
	visited[node]++;

	while(!q.empty())
	{
		int cur = q.front();
		q.pop();
		for(int i : A[cur])
		{
			if(visited[i]==-1)
			{
				visited[i] = visited[cur] + 1;
				q.push(i);
			}
		}
	}
}