벨만-포드 알고리즘, 타임머신(백준_11657)

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

11657번: 타임머신

 

문제 설명

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 것이다.

• 그래프 간 가중치가 음수가 존재한다. 
• 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 -1을 출력
• 도시 순서대로 걸린 시간을 출력
• 해당 도시로 가는 경로가 없다면 -1을 출력

 

문제에 대한 아이디어

최단거리를 구하는 알고리즘 중 가중치에 음수가 존재하므로 벨만포드 알고리즘을 사용해야 한다.

위의 그래프로 벨만포드 알고리즘 이해

 

1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기

 

2. 모든 에지를 확인해 정답 배열 업데이트하기

에지 리스트를 (노드 갯수 - 1)번 반복하면서 최단 경로 배열을 업데이트한다. 

왜 (노드 갯수 -1)번을 반복해야 할까? 

음수 사이클이 없을 때 특정 노드에 들어올 수 있는 경로를 만들 수 있는 경우가 최대 (노드 개수 - 1) 이기 때문이다.
예를 들어 5개의 노드 중 1번을 가는 최단 경로를 만든 다고 하면 결국 2,3,4,5 에서 1번으로 들어오므로 최단 경로의 개수는 최대 4개이다.

 

• 업데이트 조건 방법

1.  최단 경로 배열의 시작 인덱스 값이 무한일 경우 지나간다. (시작 인덱스 값이 무한인 경우는 아직 그 노드를 방문하지 않았다는 뜻이다.)
2. 마지막 인덱스의 값과 시작 인덱스 값 + 가중치를 비교해서 작은 값으로 바꾼다.

 

3. 음수 사이클 유뮤 확인하기

음수 사이클이 존재하면 최단 경로를 확인할 수가 없다.

그러므로 에지 리스트를 다시한번 돌면서 정답 배열이 또 업데이트되면 음수 사이클이 존재한다고 생각한다. 

예제에서는 빨간색 동그라미 친 부분이 음수 사이클이므로 이 그래프는 최단 경로를 구할 수 없는 그래프이다.

 

구현

• Edge 클래스

static class Edge{
    int start, end, edge;
    public Edge(int start, int end, int edge){
        this.start = start;
        this.end = end;
        this.edge = edge;
    }
}

• Main

public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Edge edges[] =  new Edge[m+1]; //Edge 리스트
        long distance[] = new long[n+1]; // 정답 배열
        for(int i =1; i<n+1; ++i){
            distance[i] = Long.MAX_VALUE; //정답 배열은 무한으로 초기화
        }
        //Edge 배열 입력 받기
        for(int i=0; i<m; ++i){
            st = new StringTokenizer(buf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a,b,c);
        }
        distance[1] =0; //출발 노드는 0으로 초기화
        for(int i=1; i<n; ++i) { //노드 갯수 -1 번 반복
            for(int j=0; j<m; ++j){ 
                //정답 배열의 값이 무한이면 탐색 금지
                if(distance[edges[j].start] != Long.MAX_VALUE &&
                        distance[edges[j].start]+edges[j].edge < distance[edges[j].end]){
                    distance[edges[j].end] = distance[edges[j].start]+edges[j].edge;
                }
            }
        }
        //음수 사이클인지 검사
        boolean check= true;
        for(int i=0; i<m; ++i){ 
            if(distance[edges[i].start] != Long.MAX_VALUE &&
                    distance[edges[i].start]+edges[i].edge < distance[edges[i].end]){
                check = false; //정답 배열이 또 업데이트 된거면 음수 사이클이 존재한다.
                break; 
            }
        }
        if(check == false) System.out.println(-1);
        else {
            for(int i=2; i<n+1; ++i){
                if(distance[i] == Long.MAX_VALUE) System.out.println(-1);
                else System.out.println(distance[i]);
            }
        }
    }

 

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_11657.java

GitHub - Heron-Woong/CodingTest_Practice