백준(BOJ) 1865: 웜홀

#bellman

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

(복습. 벨만포드: 음의주기가 있을때도 최단거리를 구할수 있고 음의주기가 있다면 판별할 수 있다. n번 반복하여 매번 모든 간선에 대해 dsit를 갱신한다. n-1번째에 dist가 갱신된다면 그것은 음의 주기가 있다는 것이다)

출발했던 지점으로 다시 돌아왔을때 시간이 되돌아간(시간이 줄어든)경우가 있는지를 묻고 있다. 기본적으로 벨만포드는 음의주기가 있을때를 포함하여 한점에서 다른 모든 정점까지의 거리를 구하기 위한 알고리즘이다. 그런 알고리즘이 이러한 출발정점으로 되돌아 왔을 경우에 별다른 코드 변경없이 쓰일수 있다는 것이다(물론 시간초과를 해결하기 위한 boolean변수는 필요했다).

어떻게 이것이 가능할까? 문제에서는 출발점이 어딘지도 딱히 주워지지 않는다. 그리고 굳이 다시 출발점으로 되돌아 오지 않다 하더라도 음의 주기가 있다면 그 주기를 겪고 다시 출발정점으로 돌아온다고 생각하기만 하면 그만이다. 즉 음의주기가 있는지 없는지가 중요하지 출발점으로 되돌아 올수있는가 없는가가 중요한것이 아니라는 말이다. 이러한 논리로 이 문제는 벨만포드를 이용하여 해결할 수 있다. 

또한 아래 참고링크에서와 같이 dist의 초기값을 적절한 값으로만 준다면 dist[i]!=INF라는 조건을 생략하고 단한번 벨만포드를 적용하여 문제를 해결할 수도 있다. 왜냐하면 문제에서 묻고 있는것은 시간이 줄었는지를 묻고 있는것이지 최단거리를 묻고 있는 것이 아니기 때문이다. 

https://steady-coding.tistory.com/91

두번째 풀이 보다는 느린 정석풀이

 

/*
시간초과로 엄청 고생했던 문제다. 벨만포드로 푸는 방식은 맞았다. 하지만 주된 시간초과 원인은 매번 모든 간선을 돌때
한번이라도 진전이 없으면 바로 외부루프를 빠져나가게 해주지 못해서 시간초과가 난것이다. 억울한 문제이다. 너무 크게
생각하지 않아도 된다. 
 */
 
 import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static class Edge{
        Edge(int start, int end, int weight){
            this.start=start;
            this.end=end;
            this.weight=weight;
        }
        int start;
        int end;
        int weight;
    }
    static final int INF=987654321;
    private static boolean bellman_ford(int node, List<Edge> edges, int departPos) {
        int[]dist=new int[node+1];
        Arrays.fill(dist, INF);
        dist[departPos]=0;
        boolean updated=false;
        for(int i=1;i<=node;i++){
            updated=false;
            for(var edge: edges){
                if(dist[edge.start]!=INF){
                    if(dist[edge.start]+edge.weight<dist[edge.end]){
                        updated=true;
                        dist[edge.end]=dist[edge.start]+edge.weight;
                        if(i==node){
                            return true;
                        }
                    }
                }
            }
            //출발점으로 아주 돌아오지 못하는 경우일수도 있으나 n-1번동안은 
            //꾸준히 update되었지만, n번째 update되지않은, 즉, 정상적으로 돌아왔지만 주기가 
            //존재하지 않는 경우일 수도 있다.
            if(!updated)
            	break;
        }
        return false;
    }

    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int tc=Integer.parseInt(br.readLine());
        List<Edge>edges=new ArrayList<>();
        StringTokenizer st;
        for(int t=0;t<tc;t++){
            st=new StringTokenizer(br.readLine());
            //node, edge, warmholl
            int node=Integer.parseInt(st.nextToken());
            int edge=Integer.parseInt(st.nextToken());
            int warmholl=Integer.parseInt(st.nextToken());

            for(int i=0;i<edge;i++){
                st=new StringTokenizer(br.readLine());
                int u=Integer.parseInt(st.nextToken());
                int v=Integer.parseInt(st.nextToken());
                int w=Integer.parseInt(st.nextToken());
                edges.add(new Edge(u,v,w));
                edges.add(new Edge(v,u,w));
            }
            for(int i=0;i<warmholl;i++){
                st=new StringTokenizer(br.readLine());
                int start=Integer.parseInt(st.nextToken());
                int end=Integer.parseInt(st.nextToken());
                int weight=Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, -weight));
            }
            boolean result=false;
            for(int i=1;i<=node;i++){
                result=bellman_ford(node, edges, i);
                if(result){
                    System.out.println("YES");
                    break;
                }
            }
            if(!result)
                System.out.println("NO");
            edges.clear();

        }

    }


}

 

두번째 풀이. 벨만 포드 오직 한번 사용.

첫번째 풀이보다 월등히 빠름을 볼수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Testing3{
    static class Edge {
        Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        int start;
        int end;
        int weight;
    }

    static final int INF = 987654321;

    private static boolean bellman_ford(int node, List<Edge> edges) {
        int[] dist = new int[node + 1];
        Arrays.fill(dist, INF);
        boolean updated = false;
        for (int i = 1; i <= node; i++) {
            updated = false;
            for (var edge : edges) {
                if (dist[edge.start] + edge.weight < dist[edge.end]) {
                    updated = true;
                    dist[edge.end] = dist[edge.start] + edge.weight;
                    if (i == node)
                        return true;
                }
            }
            if (!updated)//출발점으로 아주 돌아오지 못하는
                // 경우일수도 있으나 n-1번동안은 꾸준히 update되었지만,
                // n번째 update되지않은, 즉, 정상적으로 돌아왔지만 주기가 존재하지 않는 경우일 수도 있다.
                break;
        }
        return false;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        List<Edge> edges = new ArrayList<>();
        StringTokenizer st;
        for (int t = 0; t < tc; t++) {
            st = new StringTokenizer(br.readLine());
            //node, edge, warmholl
            int node = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            int warmholl = Integer.parseInt(st.nextToken());

            for (int i = 0; i < edge; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                edges.add(new Edge(u, v, w));
                edges.add(new Edge(v, u, w));
            }
            for (int i = 0; i < warmholl; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, -weight));
            }
            boolean result = false;
            result = bellman_ford(node, edges);
            if (result)
                System.out.println("YES");
            else
                System.out.println("NO");
            edges.clear();
        }
    }
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

아래는 인용글.

풀이 - 두 번째 방식

문제에서는 출발점을 알려주지 않았는데, 우리는 하나의 정점만을 택하고 벨만포드 알고리즘을 "1번"만 수행해도 음의 사이클이 발생하는지 알 수 있습니다.

 

첫 번째 방식 소스코드를 유심히 살펴보면, 중간에 dist[i] != INF 조건이 있습니다.

이것은 아직 방문하지 않은 단절된 곳을 의미하며, 이 곳을 시작점으로 삼아서 다른 곳으로 이동하는 것은 불가능합니다.

 

가령, 아래와 같은 그래프가 있다고 가정합시다.

 

 

 

 

 

 

만약, 출발점이 A라고 한다면, dist[A] = 0, dist[B] = dist[C] = INF일 것입니다. 그리고 첫 번째 풀이 방식에서 사용한 INF 조건을 추가하면, A에서는 다른 곳으로 탐색할 수가 없습니다. 하지만, B와 C에서는 음의 사이클이 발생할 수도 있습니다.

 

이 문제를 틀린 다른 사람들의 코드를 살펴 보니, 출발점은 1로 잡아 놓고, INF 조건을 추가한 경우가 많았습니다.