백준 1865번: 웜홀 (Java)

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

1865번: 웜홀

 

 

 

 

 

 

 

 

 

나의 (실패한) 접근 방법

1. 플로이드는 O(N^3)이라 일단 제외했습니다. 다만, 풀고 다른 사람의 코드를 보니 플로이드도 아슬아슬하게 제한 시간 내에 도는 거 같습니다.

2. 이후 '음수 사이클이 존재하나 확인하면 된다'는 생각에(아이디어는 맞았죠.), 양수간선은 N번의 다익스트라, 음수 간선은 벨만 포드를 돌려 각자 따로 처리한 후 반복문으로 음수 사이클이 있나 확인해보려고 했습니다만, 생각보다 방법이 번거롭기도 해서 구현을 그만뒀습니다. 아마 맞는 로직인지 가물가물한데, 된다한들 시간 초과가 뜰 겁니다.

3. '벨만-포드'에 음수 사이클을 찾는 기능이 있는건 (예전에 얼핏 공부하여) 알았지만, 당시 문제를 '시작점이 1로 고정되었다'고 잘못 읽어, '음수 사이클이 존재하더라도 음수 사이클은 음수 사이클대로 돌고, 시작점이랑 연결되지 않을 수도 있다'라는 생각이 들어 구현을 안 하고 풀이를 봤습니다. 지금 다시 생각해보면 시작점이 1로 고정되어있지 않기에 그냥 음수 사이클만 찾으면 되는 거였습니다. 

 

풀이

풀이 1. 시작점을 고정한 후 음수 사이클을 찾기

시작점을 (임의로) 1로 잡습니다. 벨만-포드 알고리즘에서 '초기 연결되어 있지 않은 상태'를 dist == INF로 두어, 어떤 edge의 시작점의 dist가 INF면 '짧은 간선 찾는 작업'을 안하고 그냥 넘어가는데, 본 문제에서는 음수 사이클만 찾으면 되기에 INF 조건이 필요없으며, 거리를 INF로 초기화할 필요도 없습니다. 시간 복잡도는 O(VE)입니다.

풀이 2. 모든 점에서부터 벨만-포드를 돌려 음수 사이클이 존재하는지 확인

벨만-포드 알고리즘의 원리 상, (INF 조건이 있는 상황에서) 음수 사이클을 찾았다는 건 '시작점에서부터 도달할 수 있는 음수 사이클이 있다'는 뜻입니다. 따라서, 각각의 점을 시작점으로 잡아, vertex의 개수 V번만큼 벨만-포드 알고리즘을 수행하여 결과를 찾을 수 있습니다. 조금 더 직관적인 풀이이나, 시간 복잡도가 O(V^2E)입니다. 약 5억번의 단위 연산을 수행하기에, 시간 초과가 걱정되고, 실제로 쌩구현하면 시간초과가 뜹니다. '제이온'님은(풀이 링크) 벨만-포드 알고리즘 구현을 'edge마다 반복문을 돌면서, 만약 어느 점에서도 최솟값 갱신이 되지 않았다면 바로 멈추는' 방식으로 시간 커팅을 해주어 '맞았습니다!'를 받았습니다.

혹시 디버깅을 하고 있다면 해당 대회 테스트케이스를 참고하세요. 

 

배운 점

벨만-포드에서 음수 사이클 찾기: 꼭 시작점에서 찾을 필요가 없기에 INF 조건이 필요가 없다.

문제 잘 읽기

만약 시작점이 고정되어있다면 '음수 사이클 찾는 풀이'가 안 될 수도 있을 듯? 음수 사이클은 존재하나, 시작점에서 웜홀만 있어서 못 돌아오는 케이스가 있을 겁니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int INF = 1_000_000_007;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            
            List<Edge> edges = new ArrayList<>();
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                edges.add(new Edge(from, to, t));
                edges.add(new Edge(to, from, t));
            }
            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                edges.add(new Edge(from, to, -t));
            }
            System.out.println(BellmanFord(1, N, edges));
        }
    }
    
    static String BellmanFord(int source, int V, List<Edge> edges) {
        long[] dist = new long[V+1];
        Arrays.fill(dist, INF);
        dist[source] = 0;
        
        for (int i = 0; i < V-1; i++) {
            for (Edge e: edges) {
                dist[e.to] = Math.min(dist[e.from] + e.dist, dist[e.to]);
            }
        }
        
        for (Edge e: edges) {
            if (dist[e.from] + e.dist < dist[e.to]) {
                return "YES";
            }
        }
        return "NO";
    };
    
    static class Edge implements Comparable<Edge> {
        int from, to;
        long dist;
 
        public Edge(int from, int to, long dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}