[Algorithm]🐿️99클럽 코테 스터디 4일차 TIL : 백준 1865 웜홀

썸네일

🔍문제

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

 

웜홀

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

🤔발상

주어진 데이터는 노드와 간선이 주어지는 그래프 형태의 데이터이며 음의 가중치가 존재합니다.
그 중에 사이클이 존재하는지 검사하는 알고리즘으로 벨만포드 알고리즘으로 풀기에 적합한 문제라 판단하였습니다.
최단거리를 찾는 방법 중 자주 쓰이는 알고리즘 3개 중 하나이며 각각의 특징은 다음과 같습니다.

• 다익스트라
  • 한 노드 사이의 최단거리를 계산
  • DP를 이용하여 빠름
  • 음의 가중치가 존재하면 사용 불가능
• 플로이드 워셜
  • 모든 노드 사이의 최단거리를 계산
  • O(N ^ 3) 시간복잡도로 느림
  • 음의 가중치가 존재해도 사용 가능
• 벨만포드
  • 모든 노드 사이의 최단거리를 계산
  • 음의 가중치가 존재해도 사용 가능
  • 음수 사이클을 감지 가능함

🔦입출력

음의 가중치가 주어진 간선은 입력 순서로 구분되며, 입력값을 전처리해주어야 합니다.

📃의사코드

- 데이터 입력
- 입력시 음의 가중치 별도 처리
- 벨만포드 알고리즘 이용, 거리 업데이트
- 사이클 검사 결과 출력

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int tc = Integer.parseInt(br.readLine());
            for (int i = 0; i < tc; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int undirected = Integer.parseInt(st.nextToken());
                int directed = Integer.parseInt(st.nextToken());
                Graph graph = new Graph(v, undirected * 2 + directed);
                graph.init(br, undirected, directed);
                graph.bellmanFord(1);
                bw.write(!graph.isCycle ? "NO" : "YES");
                bw.newLine();
            }
        }
    }
}

class Graph {

    boolean isCycle;

    class Edge {

        /**
         * source
         */
        int s;
        int dest;
        int weight;

        Edge() {
            s = dest = weight = 0;
        }

        Edge(int s, int dest, int weight) {
            this.s = s;
            this.dest = dest;
            this.weight = weight;
        }
    }

    int V, E;
    /**
     * edge
     */
    ArrayList<Edge> e;

    Graph(int v, int en) {
        V = v;
        E = en;
        e = new ArrayList<>();
        isCycle = false;
    }

    public void init(BufferedReader br, int undirected, int directed) throws IOException {
        StringTokenizer st;
        for (int i = 0; i < undirected; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, weight));
            e.add(new Edge(dest, src, weight));
        }
        for (int i = 0; i < directed; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, -weight));
        }
    }

    public void bellmanFord(int src) {
        Graph graph = this;
        int V = graph.V, E = graph.E;

        int[] dist = new int[V + 1];
        Arrays.fill(dist, 1000000000);
        dist[src] = 0;

        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < E; j++) {
                Edge edge = graph.e.get(j);
                if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                    dist[edge.dest] = dist[edge.s] + edge.weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            Edge edge = graph.e.get(i);
            if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                isCycle = true;
            }
        }
    }
}

🚀TIL

• 문제를 푸는 것보다 개선에서 굉장히 고생을 많이 하였습니다.
• 최초 풀이는 평소 익숙한 방식인 2중연결리스트로 그래프 자료구조를 구현하여 일반적인 그래프 순환탐색을 이용하여 구현하였습니다.(노드마다 모든 간선을 탐색하는게 아닌, 연결 간선만 탐색)
• 그 후 최적화 시도를 위해 연결관계를 표현하지 않고 간선만 입력받아 리스트로 저장한 뒤, 간선을 순회하는 벨만포드 알고리즘 의사코드를 작성하였는데 몇가지 오류가 발생하였습니다
  • 이전엔 발생하지 않던 오버플로 발생(Integer.MAX_VALUE로 초기화 하면 오류 발생)
  • 간선을 입력받으면서 생기는 사소한 반복문 인덱스 이슈
  • 시간제한 이슈(이는 오버플로 이슈를 우회하다 생긴 이슈)
    • 한번만 수행하면 되는 벨만포드지만 오버플로로 오답이 발생, 그런데 시작지점을 변경하여 여러번 반복수행하면 오버플로 오답이 놀랍게도 해결됨(??)
• 몇일전부터 고민하던 1시작 반복문을 for(i=0; i<n; ++i)로 개선
  • 이를 통해 배열일 경우 선언문에서만 +1 해주고 입력값을 그대로 사용가능