백준 1753번 [최단경로](C++) -yes6686- 티스토리

백준 문제 풀이: 1753 [최단경로]

---

문제 링크: https://www.acmicpc.net/problem/1753

문제 설명:

방향 그래프가 주어졌을 때, 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 만약 특정 정점으로 가는 경로가 없다면 "INF"를 출력합니다.

입력:

• 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
• 둘째 줄에 시작 정점의 번호 K가 주어집니다. (1 ≤ K ≤ V)
• 셋째 줄부터 E개의 줄에 간선 정보 u v w가 주어집니다. (1 ≤ u, v ≤ V, 0 ≤ w ≤ 10)

출력:

• 첫째 줄부터 V개의 줄에 각 정점으로 가는 최단 경로의 값을 출력합니다. 경로가 존재하지 않으면 "INF"를 출력합니다.

예시:

입력:
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력:
0
2
3
7
INF

---

문제 해결 코드

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

const int INF = 1e9; // 무한대를 나타내는 큰 값
vector<pair<int, int>> graph[20001]; // 인접 리스트
int dist[20001]; // 최단 거리 배열

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    dist[start] = 0; // 시작점의 최단 거리는 0
    pq.push({0, start}); // (거리, 정점)

    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if (cost > dist[cur]) continue; // 이미 처리된 거리보다 큰 경우 무시

        for (auto &edge : graph[cur]) {
            int next = edge.first;
            int nextCost = edge.second;

            if (dist[next] > cost + nextCost) {
                dist[next] = cost + nextCost;
                pq.push({dist[next], next});
            }
        }
    }
}

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

    int V, E, K;
    cin >> V >> E >> K;

    fill(dist, dist + V + 1, INF); // 최단 거리 초기화

    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    dijkstra(K);

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

    return 0;
}

---

코드 설명

이 코드는 다익스트라 알고리즘을 사용하여 시작 정점 K에서 다른 모든 정점까지의 최단 경로를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 다익스트라 알고리즘: 최소 힙을 사용하여 현재까지의 최단 경로를 확장하며, 각 정점에 대한 최단 경로를 계산합니다.
• 구현 세부사항:
  • graph[u].push_back({v, w}): 정점 u에서 정점 v로 가는 비용 w를 인접 리스트에 추가합니다.
  • dist[cur]: 시작 정점에서 현재 정점까지의 최단 거리입니다.
  • priority_queue: 현재까지의 최단 거리를 기준으로 정렬하여 처리합니다.
• 시간 복잡도 분석:
  • 간선 수 E, 정점 수 V에 대해 O((V + E) log V)
  • 최대 200,000개의 간선과 20,000개의 정점에 대해 효율적으로 작동합니다.

---

결과

코드는 입력된 그래프에서 시작 정점 K에서 모든 정점까지의 최단 경로를 정확히 계산하고, 경로가 없는 경우 "INF"를 출력합니다. 다익스트라 알고리즘을 사용하여 효율적으로 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!