문제

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

---

풀이

한 노드에서 모든 노드로 가는 최단 경로를 구할 때는 다익스트라 알고리즘을 이용할 수 있다. 이 문제는 간선의 가중치가 없기 때문에 BFS로도 풀 수 있다.

다익스트라: O(MlogN)

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e9 
#define MAX 300001 
using namespace std; 

// 노드, 간선, 거리, 출발 노드 
int N, M, K, X; 

// 노드 간의 연결 관계를 저장하는 배열 
vector<int> graph[MAX]; 

// 특정 노드에 대한 최단 거리 테이블 
int d[MAX]; 

void input() {
	cin >> N >> M >> K >> X; 

	// 최단 거리 테이블 초기화 
	fill_n(d, N + 1, INF); 

	// 노드 연결 정보 저장 
	for(int i = 0; i < M; i++){
		int a, b; 
		cin >> a >> b; 
		graph[a].push_back(b); 
	}
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq; 
	pq.push({0, start}); // 출발 노드로부터의 거리, 노드 번호 
	d[start] = 0; 

	while(!pq.empty()){
		// 최단 거리가 가장 짧은 노드 꺼내기
		int dist = -pq.top().first; 
		int now = pq.top().second; 
		pq.pop(); // --- O(logN) 

		// 이미 방문한 적이 있다면 무시 (최단거리 확정) 
		if(dist > d[now]) continue; 

		// 현재 노드의 인접 노드들에 대한 최단 거리 테이블 갱신 
		for(int adj: graph[now]){ // --- O(M) 
			int cost = dist + 1;
			
			if(d[adj] > cost){
				d[adj] = cost;
				pq.push({-cost, adj}); 
			}
		}
	}
}

void printResult() {
	bool found = false; 
	for(int i = 1; i <= N; i++){
		if(d[i] == K) { 
			found = true; 
			cout << i << "\n";
		}		
	}

	if(!found) cout << "-1\n"; 
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);

	input(); 

	dijkstra(X); 

	printResult(); 
	
    return 0;
}

최단 거리가 가장 짧은 노드부터 꺼내는 우선순위 큐는 내부적으로 힙으로 구현되어 있기 때문에, 삭제 연산에 O(logN)의 시간이 걸린다. 한 노드에 연결된 최대 노드 개수는 M개이므로, 최악의 경우 다익스트라 알고리즘의 시간복잡도는 O(MlogN)이다. (N: 노드 개수, M: 간선 개수)

BFS: O(M)

#include <iostream>
#include <queue>
#include <vector> 
#include <set> 
#define INF 1e9 
#define MAX 300001 
using namespace std; 

// 노드, 간선, 거리, 출발 노드 
int N, M, K, X; 

// 노드 간의 연결 관계 
vector<int> graph[MAX]; 

// 방문 여부 
bool visited[MAX];

// 출발 노드로부터의 거리가 K인 노드 번호 저장 (오름차순 정렬) 
set<int> answer;

void input() {
	cin >> N >> M >> K >> X;

	// 노드 간의 연결 관계 저장 
	for(int i = 0; i < M; i++){
		int a, b; 
		cin >> a >> b; 
		graph[a].push_back(b); 
	}
}

void bfs(int start){
	queue<pair<int, int>> q;
	q.push({0, start}); // 출발 노드로부터의 거리, 현재 노드 번호 
	visited[start] = true; 

	while(!q.empty()){ 
		int dist = q.front().first; 
		int now = q.front().second; 
		q.pop(); // --- O(1) 

		if(dist == K){ 
			answer.insert(now);

			// now의 인접 노드들은 거리가 K일 수 없으므로 넘어가기 
			continue; 
		}
 
		for(auto adj: graph[now]){ // --- O(M) 
			// 방문하지 않은 인접 노드에 대하여 
			if(!visited[adj]){  
				// 출발 노드로부터의 거리 갱신 
				q.push({dist + 1, adj}); 
				visited[adj] = true; 
			}
		}
	}
}

void printResult() {
	if(answer.empty()) {
		cout << "-1\n"; 
		return; 
	}
	
	for(auto e: answer){
		cout << e << "\n";
	}
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);

	input(); 

	bfs(X); 
	
	printResult(); 
	
    return 0;
}

큐는 FIFO (First In First Out) 구조로 먼저 들어온 원소가 먼저 삭제된다. 그리고 항상 rear에서 삽입(enqueue), front에서 삭제(dequeue) 연산이 수행되며 시간복잡도는 O(1)이다.

한 노드에 연결된 최대 노드 개수는 M개이므로, BFS로 풀면 시간복잡도가 O(M)이다. 채점 결과에서도 메모리와 시간이 다익스트라보다 조금 적게 든다는 걸 확인할 수 있다.