[백준] 18352 특정 거리의 도시 찾기

[백준] 18352 특정 거리의 도시 찾기

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

• priority_queue 기본적으로 내림차순임에 주의하자!
  -> 오름차순이 되도록 사용하고 싶은 경우 음수로 바꿔서 push하기!

풀이1

• bfs

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

int N, M;
int K;

map<int, vector<int>> adj;

vector<int> answer;

void solve(int start) {
	//<curMove, curCity>
	priority_queue<pair<int, int>> q;
	q.push({ 0, start });

	set<int> visited;

	while (!q.empty()) {
		int curMove = -q.top().first;
		int curCity = q.top().second;
		q.pop();

		if (visited.find(curCity) != visited.end()) continue;
		visited.insert(curCity);

		if (curMove > K) continue;
		if (curMove == K) {
			answer.push_back(curCity);
			continue;
		}

		if (adj.find(curCity) == adj.end()) continue;

		for (int i = 0; i < adj[curCity].size(); ++i) {
			int nextCity = adj[curCity][i];

			if (visited.find(nextCity) != visited.end()) continue;
			q.push({ -(curMove + 1), nextCity });
		}
	}
}

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

	int X;
	cin >> N >> M >> K >> X;

	for (int i = 0; i < M; ++i) {
		int A, B;
		cin >> A >> B;

		if (adj.find(A - 1) == adj.end()) {
			vector<int> vec;
			vec.push_back(B - 1);
			adj[A - 1] = vec;
		}
		else {
			vector<int> vec = adj[A - 1];
			vec.push_back(B - 1);
			adj[A - 1] = vec;
		}
	}

	solve(X - 1);

	if (answer.empty()) {
		cout << -1;
	}
	else {
		sort(answer.begin(), answer.end());
		for (int i = 0; i < answer.size(); ++i) {
			cout << answer[i] + 1 << "\n";
		}
	}

	return 0;
}

풀이2

• 다익스트라 알고리즘

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

const int INF = 987654321;

int N, M;

vector<int> dist;

vector<vector<int>> adj;

void priority_queue_dijkstra(int start){

	dist = vector<int>(N, INF);

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;

	while (!pq.empty()){
		int curW = -pq.top().first;
		int curNode = pq.top().second;
		pq.pop();

		for (int i = 0; i < adj[curNode].size(); i++){
			int nextNode = adj[curNode][i];

			if (dist[nextNode] > curW + 1)
			{
				dist[nextNode] = curW + 1;
				pq.push({ -dist[nextNode], nextNode });
			}
		}
	}
}


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

	cin >> N >> M;

	int K, X;
	cin >> K >> X;

	adj = vector<vector<int>>(N, vector<int>());
	for (int i = 0; i < M; ++i) {
		int A, B;
		cin >> A >> B;

		adj[A - 1].push_back(B - 1);
	}

	priority_queue_dijkstra(X - 1);

	vector<int> answer;
	for (int i = 0; i < N; ++i) {
		if (dist[i] == K) answer.push_back(i + 1);
	}
	if (answer.empty()) cout << -1;
	else {
		for (int i = 0; i < answer.size(); ++i)
			cout << answer[i] << "\n";
	}
	return 0;
}

📌참고자료

• 다익스트라 알고리즘 구현
  [TIL] 22-01-03