C++ 코딩테스트 강좌, 최소 비용 구하기

안녕하세요! 이번 포스트에서는 최소 비용 구하기라는 주제로 C++ 알고리즘 문제를 다뤄보겠습니다. 이 문제는 여러 상황에서 최적의 해결책을 찾는 데 유용하게 쓰이는 알고리즘 개념들을 살펴보는 좋은 기회가 될 것입니다. 이 글을 통해 우리는 문제분석, 알고리즘 선택, 코드 구현, 테스트, 그리고 최적화 방법까지 상세히 알아보겠습니다.

문제 설명

우리에게는 여러 개의 도시와 이들 사이의 도로가 있습니다. 각 도로는 특정 비용을 가지고 있습니다. 주어진 여러 도시들 간에 이동할 때, 우리의 목표는 시작 도시에서 목표 도시까지의 최소 이동 비용을 구하는 것입니다. 이를 다익스트라 알고리즘을 통해 해결할 수 있습니다.

문제 정의

다음은 문제의 수학적 정의입니다:

  • 주어진 도시의 수 n (1 이상 10,000 이하)
  • 경로의 개수 m (1 이상 100,000 이하)
  • 각 경로는 u, v, cost의 형태로 입력됩니다. 이는 도시 u에서 도시 v로 가는 비용이 cost라는 것을 의미합니다.
  • 시작 도시 start와 목표 도시 end가 주어집니다.

입력


    n m
    u1 v1 cost1
    u2 v2 cost2
    ...
    um vm costm
    start end

출력

목표 도시까지 가는 최소 비용을 출력합니다. 만약 도착할 수 없다면 -1을 출력합니다.

알고리즘 선택

이 문제는 가중치 그래프에서 최단 경로를 찾는 문제로, 대표적인 알고리즘인 다익스트라 알고리즘을 사용하여 해결할 수 있습니다. 다익스트라 알고리즘은 O((n + m) log n)의 시간 복잡도를 가지므로, 최대 입력 조건에서도 효율적으로 동작합니다.

다익스트라 알고리즘 개요

다익스트라 알고리즘의 기본 아이디어는 다음과 같습니다:

  1. 시작 노드를 선택하고, 이 노드까지의 거리를 0으로 초기화합니다.
  2. 나머지 모든 노드까지의 거리를 무한대로 초기화합니다.
  3. 현재 노드와 인접한 노드로의 거리를 계산하여, 더 짧은 거리가 발견되면 거리를 업데이트합니다.
  4. 모든 노드가 방문될 때까지 과정을 반복합니다.

문제 해결 과정

1단계: 문제 분석

주어진 입력을 통해 그래프를 구성하고, 각 도시에 대한 비용 정보를 저장할 데이터 구조가 필요합니다. 우리는 인접 리스트를 사용할 것입니다.

2단계: 코드 구현


#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<pair<int, int>> graph[10001];

void dijkstra(int start, int n) {
    vector<int> cost(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cost[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int currentCost = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentCost > cost[currentNode]) continue;

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

            if (cost[currentNode] + nextCost < cost[nextNode]) {
                cost[nextNode] = cost[currentNode] + nextCost;
                pq.push(make_pair(cost[nextNode], nextNode));
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (cost[i] == INF) {
            cout << -1 << endl;  // 도달할 수 없는 경우
        } else {
            cout << cost[i] << endl;
        }
    }
}

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

    for (int i = 0; i < m; ++i) {
        int u, v, cost;
        cin >> u >> v >> cost;
        graph[u].push_back(make_pair(v, cost));
        graph[v].push_back(make_pair(u, cost));  // 양방향 도로 가정
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start, n);
    
    return 0;
}

3단계: 코드 테스트

위 코드를 통해 입력을 테스트합니다. 예를 들어, 다음 입력을 통해 테스트를 해 볼 수 있습니다:


5 6
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1
4 5 3
1 5

위 입력은 도시 5개와 6개의 도로가 있는 경우로, 시작 도시가 1번, 목표 도시가 5번입니다. 이 경우 알고리즘은 최소 비용으로 1번 도시에서 5번 도시까지 가는 방법을 출력해야 합니다.

4단계: 최적화

다익스트라 알고리즘은 일반적으로 Priority Queue를 사용하여 구현하지만, 제한이 있는 경우에는 Fibonacci Heap 등을 사용할 수 있습니다. 그러나 이 글에서는 일반적인 Priority Queue를 사용하여 간단하고 효율적인 구현을 보여주었습니다.

결론

이번 강좌에서는 C++로 최소 비용 구하기 문제를 해결하는 방법을 살펴보았습니다. 다익스트라 알고리즘의 원리를 이해하고 이를 실제 문제에 어떻게 적용하는지 다뤘습니다. 이는 코딩 테스트를 대비하는 데 도움이 될 것입니다.

계속해서 더 많은 알고리즘 문제를 해결하는 방법을 배우고 연습하시길 바랍니다. 감사합니다!