11657번 - 타임머신

2024-03-18

#C++#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
N개의 도시가 있다.

•
한 도시에서 출발해 다른 도시에 도착하는 버스 M개가 있다.

•
각 버스는 A,B,C로 나타낸다.

•
A-시작도시, B-도착도시, C-걸리는 시간

•
C는 양수가 아닐 수 있다.

•
C=0 : 순간이동, C<0 타임머신 이동

•
1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간 구해라

문제 풀이

처음 이 문제를 보고 나는 바로 다익스트라로 풀어야겠다는 생각으로 바로 코드를 짰다.

초기 코드

C++

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

using namespace std;

int n, m;
vector<pair<int, int>> v[501];
int arr[501];

bool find() {
    priority_queue<pair<int, int>> pq;
    pq.push({0, 1});
    arr[1] = 0;
    while (!pq.empty()) {
        int node = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();
        if (node == 1 && arr[node] < 0)
            return false;
        if (arr[node] < dist)
            continue;
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i].first;
            int ndis = v[node][i].second + dist;
            if (arr[next] > ndis) {
                arr[next] = ndis;
                pq.push({-ndis, next});
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = 10000000;
    }
    if (find()) {
        for (int i = 2; i <= n; i++) {
            if (arr[i] == 10000000)
                cout << -1 << "\n";
            else
                cout << arr[i] << "\n";
        }
    } else
        cout << -1;
}

테스트 케이스를 다 정상적으로 동작을 하길래

아 껌이네..

하고 바로 제출을 했더니

메모리 초과가 나온다.

벡터와 배열이랑 이것저것 메모리를 여러개 사용해서 그런 것 같다.

근데 이걸 그렇게 안하면 도저히 해결방법이 생각이 안나서

결국 찾아봤더니

이게뭐람..

애초에 다익스트라로 푸는 문제가 아니었다.

벨만포드 알고리즘이라는 것을 사용해야했다.

벨만포드 알고리즘은 다익스트라와 비슷하지만

다익스트라는 매 반복마다 최단거리가 가장 짧은 노드 하나만 선택해서 찾지만

벨만포드는 매 반복마다 모든 간선을 다 확인한다.

그렇게 해서 코드를 다시짜면

최종 코드

C++

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

#define INF 1e9 //최댓값 설정

using namespace std;

int n, m;
vector<pair<int, pair<int, int>>> v;
long long arr[501];

bool find() {
    arr[1] = 0;
    for (int i = 1; i <= n; i++) { //n번 반복(n-1번 + 마지막 확인을 위한 1번)
        for (int j = 0; j < m; j++) { //각 노드 반복
            int from = v[j].first; //시작 노드
            int next = v[j].second.first; //다음 노드
            long long dist = v[j].second.second; //거리

            if (arr[from] == INF) //방문되지 않았다면 통과
                continue;

            if (arr[next] > arr[from] + dist) { //거리 업데이트 가능하면 업데이트
                arr[next] = arr[from] + dist;
                if (i == n) //n번째 반복에도 업데이트가 일어나면 음수 사이클 존재
                    return false;
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v.push_back({a, {b, c}});
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = INF;
    }
    if (find()) {
        for (int i = 2; i <= n; i++) {
            if (arr[i] == INF)
                cout << -1 << "\n";
            else
                cout << arr[i] << "\n";
        }
    } else
        cout << -1;
}