1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

경로에 깡패가 있어서 가중치가 마이너스인 경우가 있다. 따라서 최적 경로는 벨만 포드로 구해야 하는데, 여기에 제약 조건이 있다.

1️⃣ 이번 문제는 최소 가중치 합이 최적 경로인 일반적인 벨만 포드 문제와는 달리 최대 가중치 합이 최적 경로 이다.
2️⃣ 따라서 최적 경로를 구할 수 없는 경우는 N 번째 완화과정을 거쳐도 가중치의 합이 커지는 경로가 있는 경우이다.
3️⃣하지만 양의 사이클이 1에서 N까지의 경로에 영향을 주지 않는다면, 최적 경로는 그대로 존재하는 것임으로 상관 없다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: Bellman-ford, BFS

해설에서의 3번 양의 사이클이 존재하더라도, 1에서 N까지 가는 경로 중 어느 하나에도 영향을 주지 않는다면, 최적 경로는 존재하는 것임으로 상관 없다.를 어떻게 구현할지가 관건 이었다.

양의 사이클을 발견한다면, N에게 닿는지만 확인해주면 된다. 필자는 양의 사이클을 발견할 시, 양의 사이클이 존재했던 정점에서 N번 정점까지 BFS로 닿는지를 확인했다.

따라서 이번 문제에서 필요한 자료구조는

1️⃣ 간선 리스트
2️⃣ 인접 리스트
3️⃣ 거리 배열
4️⃣ to - from 배열 (자기 뿌리 찾기 배열: 자신에게 오는 정점을 저장)

이 되겠다.

(2) SUDO CODE 📜

0️⃣ 위에 제시한 4가지 자료구조 선언과 초기화
1️⃣ 벨만포드를 N-1번까지 진행 (dist 배열 채우면서 from-to 배열도 채우기)
2️⃣ 양수 사이클 존재 여부 확인
3️⃣ 양수 사이클이 존재한다면, 현 노드부터 BFS하여 N번 정점에 닿는지 확인
4️⃣ 닿으면 최적 경로가 될 수 없는 입력임으로 -1을 출력
5️⃣ 2번의 음수 사이클이 없으면

(3) 시간복잡도 분석 🕓

정점의 개수 N(최대 20,000), 간선의 개수 E (100)

시간 복잡도: N-1번 완화 + 음수 사이클 확인하며 BFS로 N번 정점 확인하기
O(20,000 * 100 + (20,100)) 시간복잡도는 $10^8$보다 작다

3. 구현 코드 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        solution.solution();
    }
}

class Solution {
    static int N, M;
    static int [][] edge_list;
    static ArrayList<Node> [] lists;
    static int [] dists, temp;
    static int [] where_are_you_from;
    static class Node {
        int end;
        int weight;

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

    public void solution () throws  IOException {
        input();
        if (!bellman_ford()) {
            System.out.println(-1);
            return;
        }
        StringBuilder sb = new StringBuilder();
        int i = N;
        while (i != 0) {
            sb.insert(0, i).insert(0, " ");
            i = where_are_you_from[i];
        }
        String answer = sb.toString().trim();
        System.out.println(answer);
    }
    public void input () 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());
        dists = new int [N+1];
        lists = new ArrayList [N+1];
        for (int i = 1; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }
        edge_list = new int[M][3];
        where_are_you_from = new int [N+1];
        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 weight  = Integer.parseInt(st.nextToken());
            edge_list[i] = new int [] {start, end, weight};
            lists[start].add(new Node( end, weight));
        }
        Arrays.sort(edge_list, (a,b) -> {
            if(a[0] == b[0]) {
                if(a[1] == b[1]) return a[2] - b[2];
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
    }

    public boolean bellman_ford () {
        Arrays.fill(dists, -(Integer.MAX_VALUE - 1));
        dists[1] = 0;
        for (int i = 0; i < N; i++) mitigation();
        return is_cycle_and_go_to_N();
    }

    public void mitigation () {
        for (int j = 0; j < M; j++) {
            int start   = edge_list[j][0];
            int end     = edge_list[j][1];
            int weight  = edge_list[j][2];
            if(dists[start] == - (Integer.MAX_VALUE - 1)) continue;
            if(dists[start] + weight > dists[end]) {
                dists[end]  = dists[start] + weight;
                where_are_you_from[end] = start;
            }
        }
//        System.out.println(Arrays.toString(dists));
    }

    public boolean is_cycle_and_go_to_N(){
        for (int j = 0; j < M; j++) {
            int start   = edge_list[j][0];
            int end     = edge_list[j][1];
            int weight  = edge_list[j][2];
            if(dists[start] == - (Integer.MAX_VALUE - 1)) continue;
            if(dists[start] + weight > dists[end]) {
                if(!bfs(start)) return false;
            }
        }
        return true;
    }

    public boolean bfs (int target_vertex) {
        boolean [] isVisited = new boolean[N + 1];
        ArrayDeque<Node> aq1 = new ArrayDeque<>();
        aq1.add(new Node(target_vertex, 0));
        isVisited[target_vertex] = true;

        while (!aq1.isEmpty()){
            int qSize = aq1.size();
            for (int i = 0; i < qSize; i++) {
                Node now = aq1.poll();
                for (int j = 0; j < lists[now.end].size(); j++) {
                    Node next = lists[now.end].get(j);
                    if(!isVisited[next.end]){
                        if(next.end == N) return false;
                        aq1.add(next);
                        isVisited[next.end] = true;
                    }
                }
            }
        }
        return true;
    }
}