이번에 풀어본 문제는
백준 11657번 타임머신 입니다.

📕 문제 링크

❗️코드

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

class Vertex {
    int start, end;
    int weight;

    public Vertex(int start, int end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}
public class Main {
    static List<Vertex> vertexes;
    static 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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        vertexes = 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 weight = Integer.parseInt(st.nextToken());

            vertexes.add(new Vertex(start, end, weight));
        }

        long [] dist = new long[N + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        for (int i = 0; i <= N; i++) {
            for (Vertex v : vertexes) {
                if (dist[v.start] == INF) continue;

                long tmp = dist[v.start] + v.weight;
                if (dist[v.end] > tmp) {
                    if (i == N) {
                        System.out.print("-1");
                        System.exit(0);
                    }
                    dist[v.end] = tmp;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            sb.append(dist[i] == INF ? "-1" : dist[i]).append("\n");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.print(sb);
    }
}

📝 풀이

N개의 도시가 있을 때, 1번 도시에서 출발하여 N번 도시까지 도달하는데 필요한 시간의 최솟값을 출력하는 문제입니다.
그 과정에서 사이클이 생긴다면 -1을 출력 후 종료하고, 도달할 수 없다면 해당 도시에 대해서만 -1을 출력합니다.
한 정점에서 다른 정점까지의 최단거리는 다익스트라 알고리즘을 활용하면 되지만, 본 문제에서는 가중치가 음수인 경우가 포함되어있기 때문에, 벨만포드 알고리즘을 사용하여 해결할 수 있습니다.

📜 후기

다익스트라 알고리즘으로 푼 문제가 몇 개 있었던 것 같은데, 음수 가중치를 포함했을 때는 예외가 있다는걸 모르고 쓰고 있었습니다. 이번 기회에 복습할 겸 몰랐던 개념을 잡아서 다행이네요!