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

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

다익스트라 알고리즘을 공부하면서 푼 문제이다.
다익스트라 알고리즘은 그래프의 한 지점에서 각 노드까지의 최단거리를 계산해주는 알고리즘이다.

priority_queue를 쓰지만 문제에서 간선의 정보가 모두 1이므로 queue를 사용해서 풀었다.

1. 모든 간선 정보를 vector 배열에 담는다.
2. 시작 노드를 queue에 넣고, while문을 돌린다.
3. queue에 있는 원소를 하나하나 꺼내면서, 간선 vector를 이용해 이어져있는 노드를 구한다.
4. 현재 최단거리 배열에 있는 값보다 현재 노드의 최단거리 + 1 값이 작으면 최단거리 배열을 갱신해주고, queue에 노드를 넣어준다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m, k, x;
int d[300001];
vector<int> r[300001];

void dijkstra(int s) {
	d[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < r[cur].size(); i++) {
			int next = r[cur][i];
			if (d[next] > d[cur] + 1) {
				d[next] = d[cur] + 1;
				q.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> m >> k >> x;
	for (int i = 1; i <= n; i++) {
		d[i] = 987654321;
	}

	for (int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;
		r[s].push_back(e);
	}
	dijkstra(x);
	bool check = false;
	for (int i = 1; i <= n; i++) {
		if (d[i] == k) {
			check = true;
			cout << i << endl;
		}
	}
	if (!check)
		cout << "-1";
}