글 읽기 - 인접 그래프를 활용한 벨만 포드 풀이법 질문

as00098 2년 전 0

안녕하세요 벨만 포드 알고리즘을 공부하던 중 해당 문제를 풀어봤습니다.

시작점이 어디든 상관없이 음인 사이클만 존재하면 YES, 존재하지 않으면 NO 인 코드를 작성해봤습니다.

똑같은 출발점과 도착점을 가지는 도로가 여러개 있다고 했지만, 거리가 가장 최소인 도로만 존재하면 된다고 생각해 인접 그래프를 활용,

거리가 최소인 도로가 들어올때마다 인접 그래프를 갱신하게 입력 받았습니다.

그 이후 N-1번 인접 그래프의 모든 간선 중 INF가 아닌 간선을 검사해 dp 배열을 갱신하게 하고, N번째 갱신 때 업데이트가 되면 사이클이 존재하는 것으로 판단해 true를 반환하

게 작성했습니다. 테스트 케이스와 게시판 반례는 모두 다 맞는데 도대체 어디서 틀렸는지 감을 못 잡겠네요. 도움 주시면 감사하겠습니다.

package per.jongho.gold;

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

import static java.lang.System.in;

public class BelmanFord1865 {
    static int[][] graph;
    static final int INF = 987654321;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());
        while (TC-- > 0) {
            StringTokenizer firstInput = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(firstInput.nextToken()); //정점의 개수
            int M = Integer.parseInt(firstInput.nextToken()); //도로의 개수
            int W = Integer.parseInt(firstInput.nextToken()); //웜홀의 개수
            graph = new int[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                Arrays.fill(graph[i], INF);
            }
            while (M-- > 0) {
                //도로 입력 (양방향성)
                StringTokenizer roadInfo = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(roadInfo.nextToken());//시작점
                int E = Integer.parseInt(roadInfo.nextToken());//종료점
                int T = Integer.parseInt(roadInfo.nextToken());//시간
                graph[S][E] = Math.min(graph[S][E], T);
                graph[E][S] = Math.min(graph[E][S], T);
            }
            while (W-- > 0) {
                StringTokenizer wormhole = null;
                try {
                    wormhole = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
                int S = Integer.parseInt(wormhole.nextToken());
                int E = Integer.parseInt(wormhole.nextToken());
                int T = -1 * Integer.parseInt(wormhole.nextToken());
                graph[S][E] = Math.min(graph[S][E], T);
            }
            sb.append(belmanFord(1, N) ? "YES" : "NO").append("\n");
        }
        System.out.print(sb);
    }

    static boolean belmanFord(int start, int N) {
        int[] dp = new int[N + 1];
        Arrays.fill(dp, INF);
        dp[start] = 0;

        boolean isUpdated;
        for (int i = 1; i <= N; i++) {
            isUpdated = false;
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    if (j == k) continue;
                    //j에서 k 로 가는 간선이 존재하고, 기존 k로 가는 길이가 j를 거쳐 k로 가는 길이보다 크면 갱신
                    if (graph[j][k] != INF && dp[k] > dp[j] + graph[j][k]) {
                        dp[k] = dp[j] + graph[j][k];
                        isUpdated = true;
                    }
                }
            }
            if (i == N && isUpdated) return true; //음수 사이클 발생
        }
        return false;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

인접 그래프를 활용한 벨만 포드 풀이법 질문

as00098 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말