[백준 - Java] 1865번 : 웜홀

문제

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

설명

벨만-포드 알고리즘을 이용해 문제를 해결하였다.

최단 거리를 구하는 알고리즘에는 벨만-포드, 다익스트라 알고리즘이 있다.
하지만 다익스트라 알고리즘과 달리 벨만-포드 알고리즘은 간선의 가중치가 음수인 경우에도 적용 가능하다.

그러나 음수 가중치가 사이클을 이루고 있는 경우에는 작동하지 않는다. 왜냐하면 사이클을 돌면 돌수록 해당 거리가 작아지기 때문에 최단 경로를 구하는 의미가 없어지기 때문이다.

주의할 점

1. 음수 사이클이 발생하는지 확인해야 한다.
   이 문제에서는 음수 사이클이 발생하는 경우 YES, 발생하지 않는 경우 NO를 출력한다.
2. 임의의 정점을 출발점으로 하는 경우와 여러 정점을 출발점으로 하는 경우
   -> 음수 사이클이 발생하는지 확인하는 조건을 작성할 때 주의해야 한다. (문제에서 출발점을 명시해 주지 않았기 때문에 둘 중에서 하나를 선택해서 구현하면 됨)

• 단 하나의 정점을 출발점으로 하는 경우 : 'dist[j] != INF'라는 조건이 있을 경우 출발점에서 다른 정점으로의 간선이 없어 INF인 경우 다른 정점들이 서로 음수 사이클이 만들어져도 더 이상 탐색하지 못하고 NO를 출력하게 된다. 그래서 아래와 같이 코드를 작성해야 한다.

if (dist[node.end] > dist[j] + node.weight) {
    dist[node.end] = dist[j] + node.weight;
    isUpdate = true;
}

• 여러 정점을 출발점으로 하는 경우 : 특정 정점에서 간선이 없어 탐색을 하지 못해도 다른 정점들이 탐색할 수도 있기 때문에 'dist[j] != INF'라는 조건을 넣어도 실행이 잘 된다.

if (dist[j] != INF && dist[node.end] > dist[j] + node.weight) {
    dist[node.end] = dist[j] + node.weight;
    isUpdate = true;
}

처음에 임의의 정점인 1을 출발점으로 하고 'dist[j] != INF'라는 조건을 넣었다가 제출을 했더니 9% 정도에서 틀렸습니다가 나와서 이것저것 해보다가 겨우 해결했다..

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

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

public class Main {
	
    static final int INF = 1000000000;
    static ArrayList<Node>[] nodeList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int T = Integer.parseInt(br.readLine());
		
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
			
            int N = Integer.parseInt(st.nextToken()); // 지점의 개수
            int M = Integer.parseInt(st.nextToken()); // 도로의 개수
            int W = Integer.parseInt(st.nextToken()); // 웜홀의 개수
			
            nodeList = new ArrayList[N + 1];
			
            for (int j = 1; j < N + 1; j++) {
                nodeList[j] = new ArrayList<>();
            }
			
            for (int j = 0; j < M + W; j++) {
                st = new StringTokenizer(br.readLine());
				
                int S = Integer.parseInt(st.nextToken()); // 시작 지점
                int E = Integer.parseInt(st.nextToken()); // 도착 지점
                int time = Integer.parseInt(st.nextToken()); // 줄어드는 시간
				
                if (j < M) {
                    // 도로는 방향이 없기 때문에 둘 다 추가해줌
                    nodeList[S].add(new Node(E, time));
                    nodeList[E].add(new Node(S, time));
                }
                else {
                    // 웜홀은 방향이 있지만 웜홀을 지나치는 경우 시간이 거꾸로 가기 때문에 음수로 바꾸어서 추가해줌
                    nodeList[S].add(new Node(E, -time));
                }
            }
			
            // 음수 사이클이 발생한 경우 YES, 아닌 경우 NO를 출력
            System.out.println(bellman(N) ? "YES" : "NO");
        }
		
    }
	
    public static boolean bellman(int n) {
        boolean isUpdate = false;
        int[] dist = new int[n + 1];
		
        Arrays.fill(dist, INF);
        dist[1] = 0; // 시작 지점은 0으로 초기화
		
        // 모든 지점을 N - 1번 순회
        for (int i = 1; i < n; i++) {
            isUpdate = false;
			
            // 모든 간선을 순회하는 for문
            // 음수 사이클이 있는 경우 N번째에서도 최단 거리를 찾아내기 때문에 for문을 N번까지 돌려보고 업데이트 되는지 확인해야 한다.
            // 만약 N번째에서 사이클이 발생할 경우에는 isUpdate이 다시 false로 변경되지 않기 때문에 true일 경우에는 사이클이 발생한 것
            for (int j = 1; j <= n; j++) {
                for (Node node : nodeList[j]) {
                    if (dist[j] != INF && dist[node.end] > dist[j] + node.weight) {
                        dist[node.end] = dist[j] + node.weight;
                        isUpdate = true;
                    }
                }
            }
			
            // 진행 중에 최단 거리가 하나라도 갱신되지 않을 경우 반복문 종료
            if (!isUpdate) {
                break;
            }
        }
		
        // 사이클이 발생한 경우 true 반환
        if (isUpdate) {
            return true;
        }
		
        return false;
    }

}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%231865/src/Main.java