이번에 풀어본 문제는
백준 1865번 웜홀 입니다.

📕 문제 링크

❗️코드

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 Edge2 {
    int end;
    int weight;

    public Edge2(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
}
public class Main {
    static int INF = 10000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (TC-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            // 도로
            List<List<Edge2>> map = new ArrayList<>();
            for (int i = 0; i <= N; i++) map.add(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());

                // 도로는 양방향
                map.get(start).add(new Edge2(end, weight));
                map.get(end).add(new Edge2(start, weight));
            }

            // 웜홀
            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());

                map.get(start).add(new Edge2(end, -weight));
            }

            int [] dist = new int[N + 1];
            Arrays.fill(dist, INF);
            dist[1] = 0;
            sb.append(bellmanFord(N, map, dist)).append("\n");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.print(sb);
    }
    static String bellmanFord(int n, List<List<Edge2>> map, int [] dist) {
        for (int i = 0; i <= n; i++) {
            boolean isUpdated = false;
            for (int j = 1; j <= n; j++) {
                for (Edge2 e : map.get(j)) {
                    int tmp = dist[j] + e.weight;
                    if (dist[e.end] > tmp) {
                        if (i == n) {
                            return "YES";
                        }
                        dist[e.end] = tmp;
                        isUpdated = true;
                    }
                }
            }
            if (!isUpdated) break;
        }

        return "NO";
    }
}

📝 풀이

N개의 지점으로 부터 도로 또는 웜홀을 사용하여 다른 정점으로 이동할 수 있습니다.
도로는 양방향에 양수 가중치, 웜홀은 단방향으로 음수 가중치를 가집니다.
특정 정점으로 부터 출발했을 때, 시작 위치로 다시 돌아와서 음수가 나올 경우 YES, 반대는 NO를 출력하는 문제입니다.
음수 가중치를 가지는 그래프이기 때문에, 벨만포드 알고리즘을 활용해줍니다.
임의의 시작점인 1로부터 벨만포드 알고리즘을 수행하여, 사이클이 생긴다면 YES를 출력해주면 됩니다.
이 문제의 경우, 최단거리가 아닌 사이클을 찾는 문제이므로, 방문하지 않은 정점 또한 탐색에 포함됩니다.
따라서 dist의 초기값을 무한대로 잡게 되면 overflow가 발생할 수 있기 때문에, 다른 값으로 대체 해줍니다.