개요

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이기 때문에 출력하지 않는다.

접근 방식

1. 다익스트라 알고리즘으로 접근해봤다.

   //index N일때 최대 earnGlad값
   void DijkStra()
   {
   	//거리랑 도로
   	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   	//초기화
   	minDist[X] = 0;
   	pq.push({ 0, X });
   
   	while (!pq.empty())
   	{
   		int dist = pq.top().first, curNode = pq.top().second;
   		pq.pop();
   		for (int nextNode : adj[curNode])
   		{
   			//elem까지의 최단거리가 갱신되면 
   			if (minDist[nextNode] > dist +1)
   			{
   				minDist[nextNode] = dist + 1;
   				pq.push(make_pair(minDist[nextNode], nextNode));
   			}
   		}
   	}
   
   }

전체 코드

#include <string>
#include <vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int minDist[300'001];
//시작 도시
int X;
vector<vector<int>> adj;

//다익스트라
void DijkStra()
{
	//거리랑 도로 
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	//초기화
	minDist[X] = 0;
	pq.push({ 0, X });

	while (!pq.empty())
	{
		int dist = pq.top().first, curNode = pq.top().second;
		pq.pop();
		for (int nextNode : adj[curNode])
		{
			//nextNode까지의 최단거리가 갱신되면 
			if (minDist[nextNode] > dist +1)
			{
				minDist[nextNode] = dist + 1;
				pq.push(make_pair(minDist[nextNode], nextNode));
			}
		}
	}

}

int main()
{
	int N, M, K;
	bool isAnswerFound = false;

	fill(minDist, &minDist[300'001], 300'001);
	cin >> N >> M >> K >> X;
	adj.resize(N + 1);
	for (int i = 0; i < M; i++)
	{
		int start, end;
		cin >> start >> end;
		adj[start].push_back(end);
	}
	DijkStra();
	for (int i = 1; i <= 300'000; i++)
	{
		if (minDist[i] == K)
		{
			cout << i << "\n";
			isAnswerFound = true;
		}
	}
	if(!isAnswerFound)
	cout << -1 <<"\n";
	
}

생각

거리가 1이기때문에 BFS로 풀어도 깔끔하다.
마지막에 -1 출력 하는부분을 빼먹어서 한번 틀렸다..