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

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

문제

---

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

---

 

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

 

출력

---

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

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

 

문제 풀이

---

bfs 문제, 또는 다익스트라 문제.

모든 도로의 거리가 1이기 때문에 bfs로 K 번만에 도달할 수 있는 도시들을 구할 수 있으며, 특정 도시에서 다른 도시들까지의 최단 거리를 구하는 다익스트라로도 풀 수 있다.

 

해당 문제를 다익스트라로 풀이한다.

X까지의 최단 거리를 저장할 distances 배열과, 도로들의 정보를 저장할 roads 벡터 배열을 생성한다. distances 배열은 초기에 X 도시에서부터 X 도시까지의 거리는 0이기 때문에 0으로 초기화해주고, 나머지는 현재 도달할 수 없음을 나타내는 MAX로 초기화해준다. 

<X부터 도시 i까지의 거리, 현재 탐색중인 도시 i>를 저장하는 우선순위 큐를 사용하여 distances 배열을 업데이트해준다. 우선순위 큐에서 top을 꺼내 해당 도시와 연결되어 있는 도시들을 모두 탐색한다.

이때 top을 꺼냈는데 X부터 i까지의 거리가 distances[i]보다 크다면 이미 탐색한 것으로 간주하고 연결되어 있는 도시들을 탐색하지 않는다. 연결되어 있는 도시들을 탐색할 때에는 X부터 i와 연결되어 있는 도시 nexyCity까지의 현재 최단 거리를 나타내는 distances[nextCity]보다 X부터 도시 i까지의 거리+1(i와 nextCity의 거리가 1이므로)가 더 작다면 distances[nextCity]를 해당 값으로 업데이트 하고 큐에 정보를 넣어준다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define MAX 987654321
using namespace std;
int* distances;
vector<pair<int, int>>* roads;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M, K, X;
	int start, end;
	bool canFind = false;
	cin >> N>>M>>K>>X;
	distances = new int[N];
	roads = new vector<pair<int, int>>[N];
	for (int i = 0; i < N; i++)
	{
		distances[i] = MAX;
		if (i == X - 1)
		{
			distances[i] = 0;
		}
	}
	for (int i = 0; i < M; i++)
	{
		cin >> start >> end;
		roads[start-1].push_back(pair(1, end-1));
	}
	pq.push(pair(0, X - 1));
	while (!pq.empty())
	{
		pair<int, int> current = pq.top();
		int cityNum = current.second;
		int cost = current.first;
		pq.pop();
		if (cost > distances[cityNum])
		{
			continue;
		}
		for (int i = 0; i < roads[cityNum].size(); i++)
		{
			int nextCity = roads[cityNum].at(i).second;
			if (cost + 1 < distances[nextCity])
			{
				distances[nextCity] = cost + 1;
				pq.push(pair(cost+1, nextCity));
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		if (distances[i] == K)
		{
			cout << i + 1 << "\n";
			canFind = true;
		}
	}
	if (canFind == false)
	{
		cout << -1 << "\n";
	}
	return 0;
}