[c++] 그래프 알고리즘의 적용 예시

08 Dec 2023

그래프는 정점과 간선의 집합으로 구성된 자료 구조이며, 많은 문제들을 효과적으로 해결하는 데 사용됩니다. 이번 포스트에서는 C++을 사용하여 그래프 알고리즘을 어떻게 적용하는지 살펴보겠습니다.

그래프 알고리즘을 사용한 최단 경로 구하기

가장 대표적인 그래프 알고리즘 중 하나인 Dijkstra 알고리즘은 최단 경로를 찾는 데 사용됩니다. 다음은 C++으로 구현한 Dijkstra 알고리즘의 예시 코드입니다.

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

#define INF 1e9

vector<pair<int, int>> graph[1001]; // 그래프는 각 노드마다 연결된 노드와 거리를 저장함
int dist[1001];

void Dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    dist[start] = 0;

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

        if (dist[cur] < cost) continue;

        for (int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            int nextCost = cost + graph[cur][i].second;

            if (nextCost < dist[next]) {
                dist[next] = nextCost;
                pq.push({-nextCost, next});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    fill(dist, dist + n + 1, INF);

    int start;
    cin >> start;

    Dijkstra(start);

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

    return 0;
}

위의 코드는 Dijkstra 알고리즘을 사용하여 그래프에서 특정 노드에서 다른 모든 노드로의 최단 거리를 구하는 예시입니다.

결론

C++을 사용하여 그래프 알고리즘을 적용하는 방법에 대해 살펴보았습니다. 이러한 알고리즘을 이해하고 활용하면 다양한 문제를 효과적으로 해결할 수 있습니다. 또한, 프로그래밍 언어 및 알고리즘의 적용 방법을 학습하는 것이 중요합니다.

참고 자료

Dijkstra 알고리즘에 대한 자세한 내용은 다음의 참고 자료를 참고하세요.