[BOJ] 1738. 골목길

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

접근 방법

몇 번을 트라이 한 지 모르겠ㄷㅏ...

벨만 포드라 해서 단순히 음수 cycle만 구현해 주면 될 줄 알았지만 경로를 직접 뽑아줘야했기 때문에 나에겐 더 어려웠다.

나의 개념으로는 벨만포드로 cycle구하기 + 최단 거리 밖에 구하지 못했었기 때문에 더 어렵게 다가왔었다.

경로를 직접 구하기 위한 핵심은 previous 배열이다.

값이 초기화 되는 부분의 전의 노드가 무엇인지 계속 추적 하는 것이다.

자세한 것은 코드를 보면서 이해 하도록 하자!

+이렇게 하면 왜 안되는 건지 모르겠는데 아시는 분 있으면 알려주세요 ㅠㅠ

for(int z=1; z <= N+1; z++){
            for(int i=1; i < N+1; i++){
                for(int k=0; k<ways[i].size(); k++){
                    Way way = ways[i].get(k);
                    int to = way.to;
                    int cost = way.cost;

                    if(costs[i] == Integer.MAX_VALUE) continue;
                    if(costs[to] > costs[i] + cost){
                        costs[to] = costs[i] + cost;
                        previous[to] = i;
                        if(z==N+1){

                            // this is Cycle.
                            if(to == N){
                                isCycle = true;
                            }
                        }
                    }
                }
            }
        }

Need Know

1. 벨만 포드

전체 코드 ( Java )

import java.io.*;
import java.autil.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static ArrayList<Way>[] ways;
    static Long[] costs;
    static int[] previous;
    static int[] ans;
    static ArrayList<Way> cycle = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        set();

        solve();
        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ways = new ArrayList[N+1];
        for(int i=1; i<N+1; i++){
            ways[i] = new ArrayList<>();
        }
        previous = new int[N+1];
        ans = new int[N+1];
        costs = new Long[N+1];
        for(int i=0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            ways[u].add(new Way(v,-w));
        }
        for(int i=1; i<N+1; i++){
            costs[i] = Long.MAX_VALUE;
        }
    }

    static void solve() throws IOException {
        bellmanFod();
        if(costs[N] == Long.MIN_VALUE|| costs[N] == Long.MAX_VALUE) bw.write("-1");
        else{
            Stack<Integer> queue = new Stack<>();
            queue.add(N);
            while(true){
                int peek = queue.peek();
                queue.add(previous[peek]);
                if(peek == 1) break;
            }
            while(!queue.isEmpty()){
                int popValue = queue.pop();
                if(popValue != 0){
                    bw.write(popValue +" ");
                }
            }
        }
    }

    static void bellmanFod(){
        costs[1] = Long.valueOf(0);
        for(int z=1; z <= N+1; z++){
            for(int i=1; i < N+1; i++){
                for(int k=0; k<ways[i].size(); k++){
                    Way way = ways[i].get(k);
                    int to = way.to;
                    int cost = way.cost;

                    if(costs[i] == Long.MAX_VALUE) continue;
                    if(costs[i] == Long.MIN_VALUE) costs[to] = Long.MIN_VALUE;
                    if(costs[to] > costs[i] + cost){
                        costs[to] = costs[i] + cost;
                        previous[to] = i;
                        if(z==N+1){

                                costs[to] = Long.MIN_VALUE;
                        }
                    }
                }
            }
        }
    }
}
class Way{
    int to, cost;

    public Way(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}