BaekJoon 18352번: 특정 거리의 도시 찾기(C++)

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

18352번: 특정 거리의 도시 찾기

풀이법

1) 다익스트라를 활용한다면 쉽게 풀 수 있는 문제였다.

2) 들어올 수 있는 입력 값중 N번까지의 도시가 300,000개가 될 수 있기에, 정적 배열을 사용하기 보단 동적 배열을 활용하여 문제를 풀어 주었다. (N이 작은 입력 값이 존재할 경우 메모리의 낭비가 발생할 수 있기 때문이다.)

3) X에서 시작한 각 node까지의 거리를 구하였으며, 문제에서 요구한 대로 K의 거리에 있는 node들을 ans라는 배열에 담아 오름차순으로 정렬 후 출력해 주었다.

4) 다익스트라 알고리즘은 특정 형식이 존재한다. 필자는 priority_queue를 사용하는 방식을 선호하며, 한 번 틀을 외워두고 동작 원리를 미리 익혀 둔다면, 계속 활용할 수 있으므로, 코드가 익숙치 않은 분들께서는 이해를 바탕으로 한 암기를 해보심을 추천한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, k, x;
vector<vector<int>> vec(300001);
vector<int> ans;
int dist[300001];
void dijk(int n, int x, int k)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,x });
	dist[x] = 0;
	while (!pq.empty())
	{
		int cost = pq.top().first;
		int curIndex = pq.top().second;
		pq.pop();
		if (dist[curIndex] < cost)
			continue;
		for (int i = 0; i < vec[curIndex].size(); i++)
		{
			int nextCost = cost + 1;
			if (dist[vec[curIndex][i]] > nextCost)
			{
				dist[vec[curIndex][i]] = nextCost;
				pq.push({ nextCost,vec[curIndex][i] });
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (dist[i] == k)
			ans.push_back(i);
	}

}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m >> k >> x;
	for (int i = 1; i <= n; i++)
	{
		dist[i] = 300001;
	}
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
	}
	dijk(n,x,k);
	if (ans.size() == 0)
		cout << -1;
	else
	{
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i] << "\n";
		}
	}
	
}