[백준 11657] 타임머신

정말 처음에는 ??? 했던 문제이다.

벨만포드 알고리즘을 이해하지 못하면 당연히 풀지 못해서 블로그들 보고 공부했는데, 내가 멍청한건지 이해하기 힘들었다.

그저 갓갓이신 kks227님의 블로그를 보고 1차 이해, 이 분 블로그를 보고 2차 이해했다. 두 분 블로그 모두 읽어보는걸 매우 추천한다.

아래 코드는 두 분 코드 섞였다.

1) 1차 코드 

#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
#define INF 100000000
int arr[502][502]; 
int d[502]; 
int n,m,from,to,weight;
bool flag=false;
 
int main(void){
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++)
            arr[i][j]=INF;
    } arr[1][1]=0;
    
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &from, &to, &weight);
        
        arr[from][to]=weight;
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                if(d[j]!=INF && d[k]>d[j]+arr[j][k]){
                    d[k]=d[j]+arr[j][k];
                    if(i==n)
                        flag=true;
                }
            }
        }
    }
    
    if(flag) printf("-1");
    else{
        for(int i=2; i<=n; i++)
            printf("%d\n", d[i]!=INF?d[i]:-1);
    }
    return 0;
}

제출했는데 출력초과가 뜨길래 반례를 찾아야하는데.. 역시나 한번에 못 찾고 결국엔 검색의 힘을 빌렸다. ^_T

반례는 이거

3 3

1 2 3

2 1 -1000

2 1 5

i->j로 갈 때 가중치가 한번만 받아진다는 보장은 없는데 이걸 신경 안씀ㅋㅋㅋㅋㅋ

웃긴건 i->j 값이 여러 번 받아질 수 있는건 예제3에서 이미 알려줬는데.. 언제쯤 문제 제대로 읽을래ㅠㅠㅠㅠ

2) 제출해서 통과받은 코드

#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
#define INF 100000000
int arr[502][502]; //인접행렬 (a에서 b까지 갈 때 걸리는 시간) - 갱신불가
int d[502]; //가중치 저장행렬 (기준점(여기서는 1)부터 a까지 갈 때 걸리는 시간) - 갱신가능
int n,m,from,to,weight;
bool flag=false;
 
int main(void){
    scanf("%d %d", &n, &m);
    
    // 초기화
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++)
            arr[i][j]=INF;
    } arr[1][1]=0;
    
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    
    // 입력값 저장
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &from, &to, &weight);
        
        if(arr[from][to]==INF)
            arr[from][to]=weight;
        else{
            arr[from][to]=min(arr[from][to],weight);
        }
    }
    
    // 벨만 포드 알고리즘
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){ // 시작점
            for(int k=1; k<=n; k++){ // 도착점
                if(d[j]!=INF && d[k]>d[j]+arr[j][k]){
                    d[k]=d[j]+arr[j][k];
                    if(i==n)
                        flag=true;
                }
            }
        }
    }
    
    if(flag) printf("-1");
    else{
        for(int i=2; i<=n; i++)
            printf("%d\n", d[i]!=INF?d[i]:-1);
    }
    return 0;
}

그렇지만 멍청한 나는 역시나 한번에 이해하지 못하고 그림을 그려가며 풀었다고 한다..

3) 벡터를 이용하여 푼 코드

#include<cstdio>
#include<vector>
#include<utility>
using namespace std;
#define INF 1000000000
vector<pair<int,int>> arr[502]; // 가중치 저장행렬 (갱신불가)
int dist[502]; // 최단거리 저장행렬 (갱신가능)
// 최단거리를 연산한 결과를 이 배열에 저장한다고 생각하면 된다)
int n,m,from,to,weight;
bool flag=false;
int main(void){
    scanf("%d %d", &n, &m);
    
    // 시작점과 도착점, 가중치 입력받기
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &from, &to, &weight);
        
        arr[from].push_back(make_pair(to,weight));
    }
    
    // 무한대로 채우고 시작점은 0으로 하기(자기자신은 보통 간선으로 연결되어 있지 않으니까)
    fill(dist,dist+n+1,INF);
    dist[1]=0;
    
    for(int i=1; i<=n; i++){
        // 시작점. 정확히 말하자면 하나의 정점
        for(int from=1; from<=n; from++){
            // 그 정점과 연결된 모든 다른 정점들을 탐색할 것이다.
            for(int to=0; to<arr[from].size(); to++){
                int next=arr[from][to].first; // 정점(from)과 연결된 정점
                int cost=arr[from][to].second; // 정점(from)과 정점(to)의 가중치
                
                // (1) 시작점이 무한대가 아니고
                // (2) 시작점과 연결된 정점의 값 > 시작점+(시작점과 연결된 정점까지의 가중치)
                if(dist[from]!=INF && dist[next]>dist[from]+cost){
                    dist[next]=dist[from]+cost;
                    
                    if(i==n)
                        flag=true;
                }
            }
        }
    }
    
    if(flag) printf("-1");
    else{
        // 이 문제에서는 시작점이 1이므로 1을 제외한 2부터 시작
        // dist 배열에는 최단거리가 저장되어 있는데
        // 이 최단거리가 무한대가 아니면 값이 있는 것이므로 최단거리 값을 출력
        for(int i=2; i<=n; i++)
            printf("%d\n", dist[i]!=INF ? dist[i]:-1);
    }
    return 0;
}

2차원 배열과 벡터 사용 했을 때의 시간차이가 어마무시하다