[백준 1753] 최단경로 (C#, C++) - soo:bak

문제 링크

1753번 - 최단경로

설명

방향 그래프가 주어지는 상황에서, 정점의 개수 V (1 ≤ V ≤ 20,000)와 간선의 개수 E (1 ≤ E ≤ 300,000), 시작 정점 K, 그리고 각 간선의 정보(출발 정점, 도착 정점, 가중치 1~10)가 주어질 때, 시작 정점에서 모든 정점까지의 최단 경로를 구하는 문제입니다.

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있으며, 도달할 수 없는 정점에 대해서는 INF를 출력합니다.

접근법

모든 간선의 가중치가 양수이므로 다익스트라(Dijkstra) 알고리즘을 사용할 수 있습니다.

다익스트라 알고리즘은 시작 정점에서 각 정점까지의 최단 거리를 점진적으로 확정해 나가는 방법입니다.

기본 원리는 다음과 같습니다:

1. 초기화:

• 시작 정점의 거리는 0, 나머지 정점의 거리는 무한대로 설정합니다
• 우선순위 큐에 시작 정점을 넣습니다

2. 반복 처리:

• 우선순위 큐에서 현재까지 발견된 최단 거리가 가장 짧은 정점을 꺼냅니다
• 해당 정점을 통해 인접한 정점으로 가는 경로를 확인합니다
• 더 짧은 경로를 발견하면 거리를 갱신하고 우선순위 큐에 추가합니다

3. 최적화:

• 이미 확정된 정점(큐에서 꺼낸 거리가 현재 기록된 거리보다 큰 경우)은 건너뜁니다
• 우선순위 큐를 사용하여 항상 가장 짧은 거리의 정점을 먼저 처리합니다

예를 들어, 5개 정점과 시작 정점 1이 주어지고 간선이 다음과 같다면:

• 1 → 2 (가중치 2)
• 1 → 3 (가중치 3)
• 2 → 3 (가중치 1)
• 2 → 4 (가중치 5)
• 3 → 4 (가중치 2)

처리 과정:

• 초기: 거리 = [0, ∞, ∞, ∞, ∞] (정점 1~5)
• 정점 1 처리: 2까지 2, 3까지 3 → [0, 2, 3, ∞, ∞]
• 정점 2 처리: 3까지 2+1=3(갱신 안 됨), 4까지 2+5=7 → [0, 2, 3, 7, ∞]
• 정점 3 처리: 4까지 3+2=5(7→5로 갱신) → [0, 2, 3, 5, ∞]
• 정점 4 처리: 더 이상 갱신 없음

최종 최단 거리: 1번 0, 2번 2, 3번 3, 4번 5, 5번 INF

우선순위 큐를 사용하면 각 간선을 최대 한 번씩 확인하므로 시간 복잡도는 O((V + E) log V)입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var v = input[0];
      var e = input[1];
      var k = int.Parse(Console.ReadLine()!);

      var graph = new List<(int to, int weight)>[v + 1];
      for (var i = 1; i <= v; i++)
        graph[i] = new List<(int to, int weight)>();

      for (var i = 0; i < e; i++) {
        var edge = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        graph[edge[0]].Add((edge[1], edge[2]));
      }

      const int INF = int.MaxValue;
      var dist = new int[v + 1];
      Array.Fill(dist, INF);
      dist[k] = 0;

      var pq = new PriorityQueue<(int vertex, int distance), int>();
      pq.Enqueue((k, 0), 0);

      while (pq.Count > 0) {
        var (vertex, distance) = pq.Dequeue();
        if (distance > dist[vertex]) continue;

        foreach (var (next, weight) in graph[vertex]) {
          var newDist = distance + weight;
          if (newDist < dist[next]) {
            dist[next] = newDist;
            pq.Enqueue((next, newDist), newDist);
          }
        }
      }

      for (var i = 1; i <= v; i++)
        Console.WriteLine(dist[i] == INF ? "INF" : dist[i].ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef vector<vector<pii>> vvpii;
typedef vector<int> vi;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_pq;

const int INF = INT_MAX;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int v, e, k; cin >> v >> e >> k;

  vvpii graph(v + 1);
  for (int i = 0; i < e; i++) {
    int u, to, weight; cin >> u >> to >> weight;
    graph[u].push_back({to, weight});
  }

  vi dist(v + 1, INF);
  dist[k] = 0;

  min_pq pq;
  pq.push({0, k});

  while (!pq.empty()) {
    auto [distance, vertex] = pq.top();
    pq.pop();

    if (distance > dist[vertex]) continue;

    for (auto [next, weight] : graph[vertex]) {
      int newDist = distance + weight;
      if (newDist < dist[next]) {
        dist[next] = newDist;
        pq.push({newDist, next});
      }
    }
  }

  for (int i = 1; i <= v; i++) {
    if (dist[i] == INF) cout << "INF\n";
    else cout << dist[i] << "\n";
  }
  
  return 0;
}