99클럽 코테 스터디 29일차 TIL [BellmanFord]

- 오늘의 학습 키워드 : 벨만포드 알고리즘

[문제 이름 : 타임 머신(백준 , G4)]
문제 url : https://www.acmicpc.net/problem/11657

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static ArrayList<Node>[] A;
    static int n,m;
    static long[] dist;
    static final long INF = Long.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 도시 개수
        n = Integer.parseInt(st.nextToken());
        // 버스 노선 개수
        m = Integer.parseInt(st.nextToken());

        A = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
            A[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            A[start].add(new Node(end, cost));
        }

        if(!bellmanFord(1)) {
            // 음수 사이클 존재하는 경우
            System.out.println(-1);
        } else {
            for(int i=2; i<=n; i++) {
                if(dist[i] == INF) {
                    // 도달 불가능한 경우
                    System.out.println(-1);
                } else {
                    System.out.println(dist[i]);
                }
            }
        }
    }

    static boolean bellmanFord(int start) {
        dist = new long[n+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        for(int i=1; i<n; i++) {
            for(int j=1; j<=n; j++) {
                for(Node node : A[j]) {
                    if(dist[j] != INF && dist[node.end] > dist[j] + node.cost) {
                        dist[node.end] = dist[j] + node.cost;
                    }
                }
            }
        }

        // 음수 사이클 체크
        for(int j=1; j<=n; j++) {
            for(Node node : A[j]) {
                if(dist[j] != INF && dist[node.end] > dist[j] + node.cost) {
                    return false;
                }
            }
        }

        return true;
    }

    static class Node {
        int end;
        int cost;

        Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
}

풀이 과정(풀이 시간 : 1시간)

음수 가중치가 존재하고, 사이클 여부를 확인하라는 말이 문제에 내포되어 있어 벨만포드 알고리즘을 사용해야 한다는 것을 빠르게 파악할 수 있었다.

 

1. 출발 정점, 도착 정점, 시간을 저장하는 ArrayList<Node>[] A를 선언하고, 입력값을 저장한다.

2. 벨만 포드 알고리즘을 사용한다. 초기에는 모두 INF로 값을 초기화한 다음, 출발 정점의 거리만 0으로 저장한다. 이후, 각 정점에서 이동 가능한 거리에 대해 계속 값을 갱신해 나간다.

3. 벨만포드 알고리즘 수행 이후, 음수 사이클을 체크해야 한다. 최단 거리가 갱신된 시점에서 한 번 더 이를 수행하여 거리가 갱신된다면, 이는 사이클이 있는 것을 의미한다.

for(int j=1; j<=n; j++) {
    for(Node node : A[j]) {
        if(dist[j] != INF && dist[node.end] > dist[j] + node.cost) {
            return false;
        }
    }
}

 4. 조건에 따라 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 

 

벨만포드 알고리즘이란?

• 단일 시작점 최단 경로 알고리즘으로, 음수 가중치가 포함된 그래프에서 최단 경로를 계산할 때 사용된다.
• 현재 노드에서 모든 정점과의 거리를 비교했을 때, 최소가 되는 간선을 통해 도달 가능한 거리의 합을 도출한다.
• 이렇게 해서 최단 경로를 구했음에도 불구하고, 다시 한번 각 정점에서 최단 거리를 갱신했을 때 갱신된다면, 이는 음수 사이클이 존재함을 의미한다.
  
  
  내일은 대한항공 자기소개서를 작성할 예정이다.