1916 최소비용 구하기 (80등)

1916 최소비용 구하기 (c++)

문제

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

접근 방식

Dijkstra
시작 마을에서 도착 마을까지의 최소 비용 -> (시작지점이 정해졌으니 Dijkstra로 한 행만 검사하면 최소비용 구하기 가능)

문제 풀이

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;
int N, M, startPos, endPos, a, b, c;
int arr[1'001][1'001] = {};
void Dijkstra()
{
    bool visited[1'001] = {};
    visited[startPos] = true;
    while (true)
    {
        int minNum = 0, minCost = INF;
        for (int i = 1; i <= N; ++i)
        {
            if (visited[i]) continue;
            if (minCost > arr[startPos][i])
            {
                minCost = arr[startPos][i];
                minNum = i;
            }
        }
        if (!minNum) break;
        visited[minNum] = true;
        for (int i = 1; i <= N; ++i)
        {
            // 나 자신으로 돌아가는 경우 pass
            if (i == startPos) continue;
            // 이미 길이 있고, 기존 값이 minNum을 거쳐서 가는 경우보다 더 빠른 경우 pass
            if (arr[startPos][i] <= minCost + arr[minNum][i]) continue;
            arr[startPos][i] = minCost + arr[minNum][i];
        }
    }
}

// 이 버스는 일방 통행이다.
// A 에서 B 로 가는 방법은 한가지가 아니다. (최소값 비교 필요)
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        fill(arr[i], arr[i] + N + 1, INF);
        arr[i][i] = 0;
    }
    for (int i = 0; i < M; ++i)
    {
        cin >> a >> b >> c;
        arr[a][b] = c < arr[a][b] ? c : arr[a][b];
    }
    cin >> startPos >> endPos;
    Dijkstra();
    cout << arr[startPos][endPos] << '\n';
    return 0;
}

다시 생각해 볼 점

1. 처음에 문제 읽을 때 분명 ‘A->B의 경우가 1개라는 말이 없네’라고 생각하고 적어뒀었다.
2. 하지만 계속 실패가 뜨는데도 그걸 적용할 생각을 못했다.
3. 처음에 미심쩍은 부분이 있었다면 확실히 검증하고 넘어가자.