백준11657(타임머신)

jh Seo·2023년 12월 31일

백준 벨만포드 알고리즘

백준

목록 보기

168/194

개요

백준 11657 타임머신

문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

접근 방식

벨만포드 알고리즘의 기초적인 지식

벨만포드 알고리즘에 대해 공부하며 처음 접근한 문제이다.
연습문제이다 보니 풀이를 보며 알고리즘 원리를 이해했다.

벨만포드 알고리즘은 다익스트라처럼 도시의 정보들을 담아두지만,
특이하게 음수가 나올수가 있다.

따라서 최단거리를 갱신할 때 음수 싸이클이 발생하면
각 반복문마다 제한없이 계속 줄어들수가 있다.
이 부분을 유의해서 풀어야한다.

벨만포드 알고리즘은 최단거리를 택해야한다.
일반적으로 각 정점을 한번씩만 방문하게 되므로 간선을 총 노드갯수 - 1번 지난다.

 for(int i=0;i<N-1;i++){
        for(int j=0;j<N;j++){
        //풀이
        }
}

왜 loop를 N-1번 돌아야하는가

처음에 왜 N-1번 반복하는지 몰라서 이해해보려고 노력했다.

설명하자면 k-1번 루프를 돌았을 때, 각 노드에 저장된 최단 거리는
k-1개의 정점을 거쳐오는 경로 중 최단 거리이다.

k개의 정점을 거쳐야 최단거리가 나오는 정점이 있다면
k-1번 루프를 돌았을 때는 갱신이 되었는지 알 수 없다.

따라서 모든 노드를 거쳐야만 최단거리가 나오는 정점이 있을 수도 있으므로
총 노드갯수 -1 번 루프를 돌아야한다.

싸이클 체크

하지만 코드를 보면 알겠지만 N-1번이 아닌 N번 루프를 돈다.

    for(int i=0;i<N;i++){
        //N-1번 루프에 걸쳐서 각 정점이 i+1개의 정점을 거쳐오는 최단경로 갱신
        for(int j=0;j<N;j++){

이유는 마지막 루프에서 싸이클 체크하기 위함이다.
마지막 루프에서도 최단거리값이 갱신된다면 그건 음수싸이클이 형성되어있다는 소리다.

따라서 갱신될 때, 조건문을 하나 추가해줬다.

//마지막에 갱신되는건 싸이클 발생한것.(싸이클 발생해 최단거리가 더 내려가서 갱신된것이므로)
if(i==N-1) minusCycle=true;

최단 거리를 다 계산했을 때, minusCycle이 true라면 -1을 출력해준다.

전체 코드

#include<iostream>
#include<vector>
using namespace std;
const long long INF=1e18;
int main(){
    int N,M;
    long long dist[500];
    scanf("%d %d",&N,&M);
    vector<pair<int,int>> adj[500];
    for(int i=0;i<M;i++){
        int A,B,C;
        scanf("%d %d %d", &A,&B,&C);
        //index 
        adj[A-1].push_back(make_pair(B-1,C));
    }
    bool minusCycle = false;
    //도시마다 INF로 초기화
    fill(dist,dist+N,INF);
    dist[0]=0;
    //정점이 N개일때 각 간선은 한번씩만 돌게 되므로 루프는 N-1개만 돔, N인이유는 마지막에 싸이클 확인용 
    for(int i=0;i<N;i++){
        //N-1번 루프에 걸쳐서 각 정점이 i+1개의 정점을 거쳐오는 최단경로 갱신
        for(int j=0;j<N;j++){
            for(auto &p: adj[j]){
                int nextNode= p.first, nextDist=p.second;
                if(dist[j]!=INF && dist[nextNode]>dist[j]+nextDist){
                    dist[nextNode]=dist[j]+nextDist;
                    //마지막에 갱신되는건 싸이클 발생한것.(싸이클 발생해 최단거리가 더 내려가서 갱신된것이므로)
                    if(i==N-1) minusCycle=true;
                }          
            }
        }
    }
    if(minusCycle) cout<<-1;
    else
    for(int i=1;i<N;i++){
        printf("%lld\n",dist[i]!=INF ? dist[i]:-1);
    }
}