11657번(벨만 포드)

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

11657번: 타임머신

이번 문제는 벨만 포드 알고리즘을 이용해서 푸는 문제였다.

다익스트라와 음의 가중치가 존재한다는 차이점 말고는 없는 알고리즘 로직이지만 이해하기 힘들었다..

 

아직 정확하게 이해 한 것인지도 잘 모르겠다.

정리하자면, 배열을 모두 무한 값으로 초기화하고, 시작점의 값을 0으로 지정한다.

그다음에 다익스트라와 같은 원리로 초기화 작업을 시작하는데 여기서 차이점이 발생한다.

다익스트라는 매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를  선택 했다면, 벨만 포드는 모든 간선을 전부 탐색한다.

그래서 벨만 포드는 다익스트라 알고리즘의 최적해를 항상 포함하고 있어서 시간 복잡도가 더 크다.

따라서 가중치가 음수인 간선이 존재하지 않고 양수 간선만 존재하는 경우에는 다익스트라를 사용하고 음의 간선이 존재하고,

음수 간선 순환의 유무를 판단해야 할 경우에는 벨만 포드를 사용한다.

 

벨만 포드의 동작 방식은 아래와 같다.

1.출발 노드를 설정한다.

2.최단 거리 저장 배열을 초기화한다.

3.다음의 과정을 N-1번 반복한다.

       전체 간선 E개를 하나씩 확인한다.

       각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

음수 간선 순환의 유무를 판단하기 위해서 3번의 과정을 한번 더 수행한다.

이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

 

그래서 나는 위의 동작 과정에서 전체 간선을 확인하는 부분을 간선이 아닌 노드에 초점을 두어서 구현하였다.

N번의 탐색과정을 수행하면서 1번 노드부터 N번 노드까지 각각의 노드가 인접한 모든 노드들을 탐색하는 식으로 구현하였다.

주어진 아래 예시를 들어서 보면,

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

1부터 3 번 노드에 간선이 총 4개가 있다. 그래서 1번 노드가 가지고 있는 인접 노드 2,3에 대해 탐색하고,

그 다음 2번 노드가 가지고 있는 노드 3에 대해 탐색하고,

3이 가지고 있는 노드 1에 대해 탐색하는 식으로 모든 간선을 탐색했다.

구현한 벨만 포드 로직은 아래와 같다.

public boolean bellmanFord(int R){
    Arrays.fill(dist,Integer.MAX_VALUE);
    dist[R]=0;

    for(int i=1; i<=N; i++){//N번의 최단거리 초기화 작업을 하면서 N 번째에 또 초기화가 발생하면 음수 간선 순환이 있다고 판단한다.
        for(int j=1; j< adj.length; j++){//adj.length=N+1 1부터 N번 노드의 최단거리 초기화를 작업함
            for (Node next : adj[j]) {
                if(dist[j]!=Integer.MAX_VALUE && dist[next.end]>dist[j]+ next.cnt){
                    dist[next.end]=dist[j]+ next.cnt;
                    if(i==N){
                        return true;//N-1번의 탐색이후 또 갱신이 일어난다면 음수 간선 순환이 있음
                    }
                }
            }
        }
    }
    return false;
}

 

그리고 나는 이 문제를 푸는 과정에서 출력 부분에서 줄바꿈 개행문자를 빼먹어서 시간 낭비를 하였다...

출력에 주의를 해야한다.

 

정답 코드는 아래와 같다.

package backjoon.b11657;

import java.io.IOException;
import java.io.*;
import java.util.*;

public class b11657 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Graph g = new Graph(N,M);
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            g.addEdge(u,v,w);
        }
        boolean hasCycle = g.bellmanFord(1);

        StringBuilder sb = new StringBuilder();
        if(hasCycle){
            sb.append(-1).append("\n");
        }else{
            for(int i=2; i<=N; i++){
                if(g.dist[i]==Integer.MAX_VALUE){
                    sb.append(-1).append("\n");
                }else {
                    sb.append(g.dist[i]).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}
class Graph{
    int N;
    int M;

    ArrayList<Node>[] adj;
    long[] dist;

    public Graph(int N, int M){
        this.N=N;
        this.M=M;
        adj=new ArrayList[N+1];
        for(int i=0; i<=N; i++){
            adj[i]=new ArrayList<>();
        }
        dist = new long[N+1];
    }
    public void addEdge(int u, int v, int w){
        adj[u].add(new Node(v,w));
    }
    public boolean bellmanFord(int R){
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[R]=0;

        for(int i=1; i<=N; i++){//N번의 최단거리 초기화 작업을 하면서 N 번째에 또 초기화가 발생하면 음의 사이클이 있다고 판단한다.
            for(int j=1; j< adj.length; j++){//adj.length=N+1 1부터 N번 노드의 최단거리 초기화를 작업함
                for (Node next : adj[j]) {
                    if(dist[j]!=Integer.MAX_VALUE && dist[next.end]>dist[j]+ next.cnt){
                        dist[next.end]=dist[j]+ next.cnt;
                        if(i==N){
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}
class Node{
    int end;
    int cnt;

    public Node(int end, int cnt) {
        this.end = end;
        this.cnt = cnt;
    }
}