백준 1865 웜홀 - JAVA

1865 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static List<int []> list;
    static int N;
    static int dist[];
    private static final int INF = 500 * 10_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int TC = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < TC; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            list = new ArrayList<>();
            for (int i = 0; i < M + W; i++) {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                if (i < M) {
                    list.add(new int[] {s,e,t});
                    list.add(new int[] {e,s,t});
                } else {
                    list.add(new int[] {s,e,-t});
                }
            }
            if (bellmanFord()) {
                bw.write(String.valueOf("YES\n"));
            } else {
                bw.write(String.valueOf("NO\n"));
            }
        } 
        bw.flush();
    }
    private static boolean bellmanFord() {
        dist = new int[N+1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        boolean check = false;
        for (int i = 1; i < N; i++) {//모든 최단경로 계산
            for (int[] node : list) {
                int start = node[0];
                int end = node[1];
                int time = node[2];
                if (dist[end] > dist[start] + time) {
                    dist[end] = dist[start] + time;
                    check = true;
                }
            } 
            if(!check) {
                break;
            }
        } 
        if(check) {
            for (int[] node : list) { //한번 더 계산했을 때, 최단경로가 변경된다면 음수사이클 존재
                int start = node[0];
                int end = node[1];
                int time = node[2];
                if (dist[end] > dist[start] + time) {
                    return true;
                }
            }
        }
        return false;
    }
}

 

알고리즘 설명

---

벨만-포드 알고리즘은 음의 가중치를 포함한 방향 그래프에서 최단 거리를 구할 수 있는 알고리즘입니다. 또한 이 알고리즘은 음수 사이클이 존재하는지도 판별할 수 있습니다. 최단 거리를 구하기 위해서는 N-1번 반복해야 하는데, 그 이유는 음수 사이클이 없다면, N개의 노드에 대해 최단 거리가 될 수 있는 간선의 최대 개수가 N-1개이기 때문입니다. 쉽게 말해, 최단 거리를 구할 때, 아무리 많은 시간이 걸려도 최대 N-1개의 간선을 넘길 수 없다는 뜻입니다. 이후, 최단 거리 값은 dist 배열에 저장되고, 반복문을 통해 dist 배열을 계속해서 업데이트합니다. 시간과 메모리를 절약하기 위해 check라는 boolean 변수를 사용하고, 반복문을 한 번 돌았을 때 dist 배열의 값이 더 이상 갱신되지 않으면 최단 거리 구하는 반복문을 종료합니다. 이는 간선완화가 더 이상 되지않으면, 음수 사이클이 없는것으로 판단되기 때문입니다. 만약 반복문이 check가 true인 채로 종료되면, list 내의 간선들을 한 번 더 돌며 dist 배열 값이 줄어드는지 확인합니다. 만약 더 이상 값이 줄어들지 않으면 음수 사이클이 존재하지 않는다고 판단할 수 있습니다.

노드번호 1만 시작점으로 설정하고 반복적으로 순회하지 않는 이유는, list에 저장된, 모든 간선을 순회하면서, 모든 노드간의 음수사이클 유무를 판별할 수 있기 때문입니다.

 

생각보다는 간단한 알고리즘이지만, 저는 문제에서 노드가 끊어져 있을 수 있다는 점을 고려하지 못하고, if(dist[end] > dist[start] + time) 조건을 if(dist[start] != INF && dist[end] > dist[start] + time)로 설정하여 출발노드 1과 끊어져 있는 노드에 대해서는 음수 사이클을 판별하지 않도록 하는 실수를 저질렀습니다. dist[start] != INF라는 조건을 달게되면, 시작노드인 노드 1과 끊어져있는 노드의 경우에는 dist[]의 값이 초기값인 INF에서 변하지 않아, 음수사이클 판별에서 제외되기때문입니다.

 

- 참고 -

간선완화(Edge Relaxation) : 두 노드 간의 최단 거리가 더 줄어들 수 있다면 그 거리를 갱신하는 것 또는 과정.

 

고민했던 부분

---

간선 저장을 객체로 저장해야 할지, 배열에 저장할지에 대한 고민을 했었습니다. 다만, 객체 저장방식은 각 노드마다 연결된 노드를 찾기위해 탐색해야하는 과정이 있지만, 배열의 경우에는 배열에 담긴 간선을 차례대로 연속적으로 탐색하기 때문에, 캐시가 접근하는 공간 지역성 부분에서 더 우위를 차지합니다. 또한, 배열 저장방식은 연속된 메모리에 저장되므로 코드 실행 시, 메모리 접근 속도가 객체에 비해 빠릅니다. 하지만, 객체 저장 방식은 각 노드의 간선 정보를 유연하게 다룰 수 있기 때문에 복잡한 구조나 동적 추가/삭제가 필요한 경우에 유리할 수 있습니다. 저장방식에 따른 차이를 간단하게 표로 정리해드리겠습니다.

 

객체 지향적인 코드가 당연히 더 유연한 설계는 가능합니다... ㅎㅎ 역시 CS지식은 시간이 지날수록 더 중요해지는 것 같습니다.

 

코드 해석

---

배열 리스트를 선언하고, 도로의 경우는 s와 e를 번갈아 배열에 저장하고, 웜홀의 경우에는 가중치를 마이너스로 설정하고, 단방향 저장을 실행합니다. 출발 노드인 1번 노드를 기준으로 최단 경로를 계산. N-1번 반복을 통해 각 간선에 대해 최단 경로를 계산합니다. 이때, dist[end] > dist[start] + time이면 dist[end]를 갱신합니다. 한 번의 반복에서 경로가 갱신되지 않으면 더 이상 경로가 변경되지 않는다고 판단하여 종료합니다.

N-1번 반복 이후, 한 번 더 모든 간선을 확인하여 최단 경로가 갱신된다면, 이는 음수 사이클이 존재한다는 의미이므로 true를 반환하고, 음수 사이클이 없다면 false를 반환합니다. 각 테스트케이스에 대하여 실행한 bellmanFord()함수의 결과값을 순서대로 출력합니다.