벨만포드. 타임머신

Jung In Lee·2023년 1월 7일
0

문제

  • 음의 가중치를 갖는 문제이다.
    양의 가중치만 있는 다익스트라와 달리, 다른 방법을 도입해야한다.
  • 그 방법으로는 벨만포드가 있는데, 벨만포드는 O(VE)의 시간복잡도를 가진다.
    (개선된 다익스트라는 PriorityQueue를 사용하기 때문에, O(E log V) 정도밖에 안가짐.)
    벨만포드는 그러므로 모든 간선을 살펴보기 때문에 음의 가중치를 반영할 수 있다.

해결방향성

  • 우선 벨만포드 알고리즘을 사용하기위해 기존의 Vertex 클래스 대신에, Edge클래스를 선언한다. 그 원소로는 start, end, weight를 둔다.
  • 또한, 그래프를 그릴때도, 기존의 두개의 ArrayList를 선언했던것과 다르게, ArrayList를 하나만 선언하고, 원소는 Edge로 둔다.
    (벨만포드는 간선을 중점으로 생각한다.)
    이 문제는 또한 최단경로를 구하기위해 int[] 배열이 아닌 long[] 배열을 사용해야한다.
    (사실, 변수 범위에 해당하는 맥시멈 값을 조절하는 방법을 찾는데 나도 애를 먹고있기때문에, 더 공부가 필요하다.)
  • 마지막으로 함수는, boolean으로 선언해서 음의 순환이 포함되는지 여부를 확인하는게 좋다.
  • 아 그리고, 진짜 마지막으로 반복문중 V번째 반복시, 최단경로가 변경된다면, 음의 순환이 존재하는것이다. (그때, return.)

코드

import java.io.*;
import java.util.*;

class Edge{
    private int start;
    private int end;
    private int weight;

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

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public int getWeight() {
        return weight;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());


        // 그래프 그리기
        ArrayList<Edge> graph = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph.add(new Edge(start, end, weight));
        }

        // 음수 간선 순환 : -1 break, 경로가 없으면 -1
        // 나머지 출력

        // 음수간선의 최단경로 구하기.
        long[] minway = new long[V + 1];
        Arrays.fill(minway, INF);
        boolean isNegativeCycle = BelmanFord(graph, minway, V, E);

        for (int i = 2; i <= V; i++) {
            if (isNegativeCycle) {
                bw.write(String.valueOf(-1) + "\n");
                break;
            } else if (minway[i] == INF) {
                bw.write(String.valueOf(-1) + "\n");
            } else {
                bw.write(String.valueOf(minway[i]) + "\n");
            }
        }


        bw.flush();
        br.close();
        bw.close();
    }

    private static int INF = 60_000_000;
    private static boolean BelmanFord(ArrayList<Edge> graph, long[] minway, int V, int E) {
        // visited는 없어도됨. 어짜피 모두 거쳐야함.
        // O(VE) : priorityQueue 없어도됨.
        // minway 초기화
        minway[1] = 0;

        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < E; j++) {
                Edge edge = graph.get(j);
                int edgeStart = edge.getStart();
                int edgeEnd = edge.getEnd();
                int edgeWeight = edge.getWeight();

                // INF와 더했을때 INF-1이 되면 걸러지지않는다
                if (minway[edgeStart] != INF && (edgeWeight + minway[edgeStart] < minway[edgeEnd])) {
                    minway[edgeEnd] = minway[edgeStart] + edgeWeight;
                    if (i == V) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

}

결론

  • 벨만포드 알고리즘은 최단경로 초기화에 사용된 INF 값을 포함하여 갱신하면 안된다. 음의 가중치가 포함되어있어, INF - 1이되면, 조건에 벗어나 그대로 값이 출력되기때문에, 이것도, 조건에 포함시킨다.
    (기존의 visited배열이 사라진 대신에 이런 조건이 포함된다 생각해도 뭐... 외우기 무방하다.)
  • 시간 복잡도가 O(VE)이므로 외워두면 알고리즘 짜기 편리하다.
  • 또한, visited 배열이 없어서 전부 확인한다는 것도 다시 반복해서 알아두자.
  • 현재 다익스트라, 벨만 포드 모두 맥시멈 범위를 조절하느라 애먹고있다. 어떻게 하면 범위를 잘 조절할수있을지 문제를 계속 풀어보자.
profile
Spring Backend Developer

0개의 댓글