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

걸린 시간: 13m50s

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

11 ---> 2
2 |    / |
3 |   /  |
4 V  /   V
5  3     4

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

C++ 코드

1#include <bits/stdc++.h> 
2using namespace std; 
3
4#define INF 0x7FFFFFFF
5
6typedef vector<vector<int>> vvi;
7
8void dijkstra(int V, int src, int x, vvi &graph)
9{
10  vector<int> dist(V, INF);
11  dist[src] = 0;
12
13  priority_queue<int> pq;
14  pq.push(src);
15
16  while(!pq.empty())
17  {
18    int r = pq.top();
19    pq.pop();
20
21    for(auto &v : graph[r])
22    {
23      int cost = dist[r] + 1;
24      if(dist[v] > cost)
25      {
26        dist[v] = cost;
27        pq.push(v);
28      }
29    }
30  }
31
32  bool printed = false;
33  for(int i=0; i<V; ++i) {
34    if(dist[i] == x)  {
35      printed  = true;
36      printf("%d\n", i);
37    }
38  }
39
40  if(!printed) printf("-1\n");
41}
42
43int main() {
44  int n, m, k, s;
45  scanf("%d%d%d%d", &n, &m, &k, &s);
46  vvi graph(n+1);
47
48  for(int i=0; i<m; ++i) {
49    int s, d;
50    scanf("%d%d", &s, &d);
51    graph[s].push_back(d);
52  }
53
54  dijkstra(n+1, s, k, graph);
55
56  return 0;
57}

시간 복잡도

• M개의 단방향 거리 입력 - O(M)
  • graph[s].push_back(d) - edge만들기 - O(1)
• 다익스트라
  • 도시 개수 - O(V), V = num of cities
  • 우선순위 큐 top() - O(1)
  • 단방향 거리 cost확인 - O(E), number of edges
    • 우선순위 큐 push() - O(logn)
    • 우선순위 큐 pop() - O(2logn)
• 거리가 k인지 확인하고 출력 - O(V)
• 최종 시간 복잡도: O(M) + O(V + E・logV)

공간 복잡도

• V개의 도시 - O(V)
• E개의 단방향 거리 - O(E)
• 최종 공간 복잡도: O(V + E)