[백준]1865번 웜홀

1865번: 웜홀

음수간선이 존재하는 문제였다.

bfs로 고민하니 뭔가 cycle이 생기고 왔던 노드를 다시 지나고 하는것이 어떻게 해야할지 모르겠었다.

심지어 최단거리 문제를 푼지 오래되어 디익스트라도 생각나지 않았었지만, 디익스트라도 아니었다.

처음으로 벨만포드문제를 접하게 되었다.

사실 아직 벨만포드알고리즘이 다 이해가 되지는 않는다.

• 디익스트라가 그리디한 방식 (현재까지 노드중 최소비용을 가지면서, 아직 확정된 최소비용을가진 노드가 아닌 노드를 선택하여, 해당 노드를 거친 경로를 최소비용으로 갖는 인접노드의 dist[adj_node]를 업데이트하는 방식) 이었는데,
• 벨만포드는 이에비해 확실히 완전탐색적인 모습을 보이는 것은 이해가 된다.
  • —>따라서 디익스트라의 과정 또한 여기에 포함되기 때문에, 무조건 해를 구할 수가 있다.
  • —> 그만큼 확실히 느리다 ( O(VE) )
• 또한 음의간선으로 인하여, 사이클이 생겨( 왜냐하면 "최단경로"를 구하는 것을 목표로 하기 때문에, 어떤 경우, 음의간선으로 인하여, 해당 edge를 지나는 것을 "반복!!" 할수록 더 작은 값이 나와 무한히 반복되는 경우가 생기기 때문 ), - INFINITY 값을 갖게 되는 경우도 이해가 된다.

하지만 동작 방식 자체는 이해가 잘 되지 않아 일단은 보편적으로 벨만포드 알고리즘 문제를 푸는 방식만을 생각했다.

• 현재는 이해가 다 되진 않지만 개인적으로 설명이 좋다고 생각되는 글

  벨만-포드 알고리즘

• 일단, 가장 중요한것은, 벨만포드던, 디익스타라던, 특정한 노드로부터, 각 노드까지의 최단경로를 구하는 방식이라는 것이다.

  • 따라서, 두 방식 모두 "각 노드까지의 최소비용"을 저장하는 dist table이 있을 때
  • dist table을 INFINITY값으로 초기화 한 후
  • 시작점 만을 0으로 두고 시작한다는 공통점이 있었다.

• 벨만포드는, 후에, node의 개수를 v라고 한다면, v-1 번만큼 다음을 반복한다.

  • 모든 edge에 대하여 다음을 수행한다.
    • edge 는 { from, to , cost } 를 갖고 있다.
    • dist[from]≠ INFINITY && dist[to]>dist[from]+cost —> dist[to] = dist[from]+cost 로 업데이트한다.
      • dist[from]≠ INFINITY 는 즉, from 노드를, 방문한 적 있는 경우.

• 벨만포드는, "음수간선"으로 인한 사이클의 존재를 확인할 수 있다. 위의 반복하는 과정을 한 번 더 수행한다.

  • 모든 edge에대하여 다음을 수행한다.
    • edge 는 { from, to , cost } 를 갖고 있다.
    • dist[from]≠ INFINITY && dist[to]>dist[from]+cost —> dist[to] = dist[from]+cost 로 업데이트한다.
      • dist[from]≠ INFINITY 는 즉, from 노드를, 방문한 적 있는 경우.
    • v번째에 수행하는 이 반복에서, 또다시 dist table의 update가 일어났다는 것은, 음순간선으로 인한 사이클이 발생함을 의미한다.

이 문제에 대한 정리를 해 주신 분이 있다

글 읽기 - 풀이 및 논란 완전히 정리합니다.

하지만 벨만포드도 다 이해가 되지 않았기에 이 분의 글에서 내가 이해할 수 있는 부분만을 뽑아서, 다시 풀었다.

맞았습니다가 떴지만 완전히 이해하지 못했다.

이 문제는

• 시작점이 주어지지 않아있다.
• 기본적으로 생각하게 되는 벨만포드 알고리즘은, 특정한 시작점으로부터, 음수간선이 존재하는 그래프 상에서, 각 노드까지의 최단거리를 찾는 알고리즘이다.
• 그런데 이 문제의 경우, 만약 그냥 "1"을 시작점으로 생각하고 푼다면, 1을 시작점으로 했을 때 찾을 수 없는 음수간선 사이클이 존재할 수 있다 .
• 따라저 모든 노드가 시작점이 될 수 있는 방식으로 풀어야 한다고 한다. 이는 즉, 모든 노드를 시작점으로 동시에 탐색을 시작하는 것으로 볼 수 있다. —> dist table의 모든 노드에 대한 값을 INF가 아닌 0으로 세팅한다.
  • 따라서, 이 부분
    • 벨만포드는, 후에, node의 개수를 n라고 한다면, n-1 번만큼 다음을 반복한다.
      • 모든 edge에 대하여 다음을 수행한다.
        • edge 는 { from, to , cost } 를 갖고 있다.
        • dist[from]≠ INFINITY && dist[to]>dist[from]+cost —> dist[to] = dist[from]+cost 로 업데이트한다.
          • dist[from]≠ INFINITY 는 즉, from 노드를, 방문한 적 있는 경우.
    • 여기에서, dist[from]≠ INFINITY 을 확인할 필요가 없다.
  • 그런데 이렇게 될 경우, dist 테이블이 업데이트 되는 경우는, 음의간선을 지나는 경우만 해당되게 된다.
  • 따라서 모든 edge에 대한 relaxation을 n-1번 반복했다면, cycle순환 없이 , 어떤 한점으로부터 해당 노드까지의 최단 경로가 세팅이 되었어야 한다.
  • n번째에 "모든 edge에 대한 relaxation"을 할 때에도 update가 있다면, "어떤 한 노드로부터"의 최단 경로에서, 음수간선 으로 인한 cycle 순환이 일어나고 있음을 의미한다.
  • 라고 이해했다.

구현에 있어서

• 도로는 양방향 웜홀은 단방향이기 때문에
• 특정 from, to 의 edge에 대해 최소의 cost만을 저장하고자 하였다. 노드의 개수가 500개 밖에 되지 않기 때문에 matrix를 사용하였다.

public class Main {
    public static final int TIME_INIT = 10001;
    public static int n,m,w; // the number of nodes, edges, holes
    public static int[][] matrix = new int[500][500];
    //public static List<int[]>[] graph = new ArrayList[500];
    public static List<int[]> edges = new ArrayList<>();
    public static int[] dist = new int[500];
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int test =0,v1=0,v2=0,c=0;
        test = Integer.parseInt(br.readLine());
        for(int t=0;t<test;t++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            // init dist table as the start node is 0
            Arrays.fill(dist, 0);
            // init matrix
            for(int i=0;i<n;i++)
                Arrays.fill(matrix[i],TIME_INIT);
            // get the  edge info
            for(int e=0;e<m;e++){
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken())-1;
                v2 = Integer.parseInt(st.nextToken())-1;
                c = Integer.parseInt(st.nextToken());
                if(matrix[v1][v2]>c) matrix[v1][v2]=c;
                if(matrix[v2][v1]>c) matrix[v2][v1]=c;
            }
            // get the hole info
            for(int h=0;h<w;h++){
                st = new StringTokenizer(br.readLine());
                v1 = Integer.parseInt(st.nextToken())-1;
                v2 = Integer.parseInt(st.nextToken())-1;
                c = Integer.parseInt(st.nextToken())*(-1);
                if(matrix[v1][v2]>c) matrix[v1][v2]=c;

            }

            boolean res =solve();
            if(res) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    public static void print(){
        System.out.println();
        for(int i=0;i<n;i++){
            System.out.print(dist[i]+",");
        }
    }
    // if return true --> it has cycle of negative edge
    public static boolean solve() {
        //  n 번 수행하는 것은, 음의간선 순회를 확인하기 위함.
        int cur=0,next=0,c=0;
        for(int i=0;i<n;i++){
            // 모든 간선에 대하여 수행 한다. 간선을
            for(int start=0;start<n;start++){
                for(int end=0;end<n;end++){
                    // 이거는 간선이 아님
                    if(matrix[start][end]==TIME_INIT)continue;

                    // 갱신이 일어나는 경우
                    if(dist[end]>(dist[start]+matrix[start][end])){
                        dist[end]=dist[start]+matrix[start][end];
                        //print();
                        if(i == n-1) return true;
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        Setting();

    }
}