[알고리즘] (bfs 유형) 최단거리의 도시 찾기

문제

어떤 나라에는 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입 니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한 출발 도시 ※에서 출발 도시 X로 가 는 최단 거리는 항상 0이라고 가정합니다.

예를 들어 N = 4, K = 2, X = 1일 때 다음과 같이 그래프가 구성되어 있다고 합시다. 이때 1번 도시에서 출발하여 도달할 수 있는 도시 중에 서, 최단 거리가 2인 도시는 4번 도시뿐입니다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않습니다.

입력

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K. 출발 도시의 번호 X가 주어집니다.

(2 ≤ N 5 300.000. 1 ≤ M ≤ 1,000,000,1 ≤ K ≤ 300.000. 1 ≤ X 5N)

• 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어지며, 각 자연수는 공백으로 구분합니다.

이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미입니다. (1 S A, B S N) 단

A와 B는 서로 다른 자연수입니다.

출력

• X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩

오름차순으로 출력합니다.

• 이때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력합니다.

IDEAS

얼마만큼의 거리가 걸리는지ㄹ를 찾아야 하는 문제는 주변부터 하나씩 탐색을 하는것이기에 bfs가 적합한것 같다.

typedef	struct	s_node
{
	int	idx;
	int	depth;
}				node;

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

int	main(void)
{
	std::vector<int>	result;
	int	cnt = 0;
	int	**map;
	int	N, M, K, X;

//인자 받기.
	std::cin >> N >> M >> K >> X;
	std::cin.ignore();
	map = new int*[M];
	for (int i=0; i<M; i++)
		map[i] = new int[2];
	for (int i=0; i<M; i++)
		std:: cin >> map[i][0] >> map[i][1];
	std::cin.ignore();

//queue 생성
	std::queue<node> q;
	node	departure;
	departure.idx = X;
	departure.depth = 0;
	q.push(departure);
	while (!q.empty())
	{
		node	now = q.front();
		// std::cout << now.idx << std::endl;
		q.pop();
		for (int i=0; i<M; i++)
		{
			if (map[i][0] == now.idx)
			{
				node	next;
				next.idx = map[i][1];
				next.depth = now.depth + 1;
				if (next.depth == K)
					result.push_back(next.idx);
				else
					q.push(next);
			}
		}
	}

	for (int i=0; i<result.size(); i++)
	{
		std::cout << result.back() << std::endl;
		result.pop_back();
	}
}