백준 11779번: 최소비용 구하기 2 (Python, C++)

접근

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

11779번: 최소비용 구하기 2

백준 사이트의 알고리즘 문제집을 순서대로 하나씩 풀어보는 방식으로 C++ 를 이용한 풀이를 하고있는데, 아직 안풀었는데 실패인 문제가 있어 보니 이전에 python으로 통과하였는데 재채점으로 시간초과가 된 문제였다. C++로 다시 풀어보고, 비슷한 방법으로 Python 코드도 수정하여 둘다 풀이 완료하여 코드를 수정했다.

---

전에 문제들과 비슷하게 DP와 BFS 알고리즘으로 구할 수 있다.

dp[i]에 [시작 위치부터 i 지점까지의 최소 비용, 최소 비용일 때의 직전 도시] 를 저장한다고 생각하고 코드를 보면 쉽게 이해할 수 있다.

특정 위치를 순환할 때마다 다음의 작업을 해준다.

(현재 위치의 최소 비용 + 다음 위치까지의 비용) < (다음 위치의 최소 비용) 일 때,

1. 다음 위치의 최소비용 = 현재 위치의 최소 비용 + 다음 위치까지의 비용
2. 다음 위치의 직전 도시 = 현재 도시
3. queue에 다음 위치 추가

q가 없어질 때까지 순환하고 나서 dp를 이용하여 목적지의 최소 비용과 직전 도시를 알 수 있다.

직전 도시를 따라가면서 경로를 저장해주면 경로 또한 구할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
bus = [[float("inf")] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    bus[a][b] = min(bus[a][b], c)
s, e = map(int, sys.stdin.readline().split())
dp = [[float("inf"), -1] for _ in range(n + 1)]
dp[s] = [0, 0]
q = [s]
while q:
    now = q.pop(0)
    for dest in range(1, n + 1):
        if dp[now][0] + bus[now][dest] < dp[dest][0]:
            dp[dest][0] = dp[now][0] + bus[now][dest]
            dp[dest][1] = now
            q.append(dest)
print(dp[e][0])
res = [e]
tmp = e
while tmp != s:
    res.append(dp[tmp][1])
    tmp = dp[tmp][1]
print(len(res))
print(*res[::-1])

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 1001
#define INF 1000 * 100000 + 1
#define nINF 100001

int N;
int M;
int MAP[MAX_N][MAX_N];
long long dp[MAX_N][2];

int MinVal(int a, int b) {
    if (a <= b) {
        return a;
    } else {
        return b;
    }
}

void bfs(int a) {
    queue<int> Q;
    Q.push(a);
    dp[a][0] = 0;
    dp[a][1] = 0;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int i = 1; i <= N; i++) {
            if (MAP[now][i] == nINF) continue;
            if (dp[i][0] <= dp[now][0] + MAP[now][i]) continue;
            dp[i][0] = dp[now][0] + MAP[now][i];
            dp[i][1] = now;
            Q.push(i);
        }
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N >> M;
    int a, b, c;
    for (int i = 1; i <= N; i++) {
        dp[i][0] = INF;
        dp[i][1] = -1;
        for (int j = 1; j <= N; j++) {
            MAP[i][j] = nINF;
        }
    }
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        MAP[a][b] = MinVal(MAP[a][b], c);
    }
    cin >> a >> b;
    bfs(a);
    cout << dp[b][0] << endl;
    vector<int> path;
    path.push_back(b);
    while (b != a) {
        b = dp[b][1];
        path.push_back(b);
    }
    cout << path.size() << endl;
    for (int i = path.size() - 1; 0 <= i; i--) {
        cout << path[i] << ' ';
    }
    cout << endl;

    return 0;
}

더 생각해 볼 것?

C++로 풀 때에는 float('inf')로 무한대를 표현하는 파이썬과는 달리 INF의 값을 숫자로 정해주게 되는데, 이 INF 값이 문제에서 주어진 INF 값을 만족하는지 한번 더 확인해보아야겠다. 이번 문제에서는 도시 사이의 거리가 100,000 이고, 1,000 개의 도시를 지날 수 있기 때문에 이 INF 값은 1000 * 100000 까지 가능하다는 점을 확인해야 하며, 혹시 이 값이 int 값의 범위를 넘는지도 문제를 풀 때 체크할 만한 포인트인것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!