[백준][C++]18352번. 특정 거리의 도시 찾기

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

 

그래프를 입력받고 BFS를 통해 X부터 경로를 탐색하면서 각 도시 까지의 거리를 기록한다.

BFS를 통한 순회가 끝나면 x로 부터 k거리에 있는 도시를 오름차순으로 출력해주면 된다.

 

정답코드

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

using namespace std;

void BFS(int node);

vector<vector<int>> cities;
vector<int> visitied;
vector<int> answer;
int main()
{
	int n, m, k, x;

	cin >> n >> m >> k >> x;

	cities.resize(n + 1);

	//그래프 입력받기
	for (int i = 0; i < m; i++)
	{
		int s, e;
		cin >> s >> e;
		cities[s].push_back(e);
	}

	visitied.resize(n + 1);

	//초기값 세팅
	for (int i = 0; i <= n; i++)
	{
		visitied[i] = -1;
	}

	BFS(x);

	for (int i = 0; i <= n; i++)
	{
		if (visitied[i] == k) answer.push_back(i);
	}

	if (answer.empty()) cout << "-1" << "\n";
	else
	{
		sort(answer.begin(), answer.end());
		for (int tmp : answer)
		{
			cout << tmp << "\n";
		}
	}
}


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

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