글 읽기 - 어디가 문제일까요? 눈 빠지겠어요 ...

calgarylof 2년 전 0

1.벨만 포드로 출발 도시부터 모든 도시의 최소 비용을 계산한다.

2.도시의 수가 N일 때, N-1만큼 모든 노선의 수 M번 확인한다.

3.한번 더 M개의 노선을 확인했을 때 거리가 저장된 배열이 업데이트 된다면 음수 사이클이 존재하는 것이다.

제가 이해한 내용인데 구현한 코드 중 어디가 잘못되었는지 잘 모르겠습니다..

60%에서 계속 틀리네요

처음에 노선 정보를 저장할 때 Bus[] 배열을 사용하다가 List로 바꾸어주었어요

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

public class Main {

	static final long INF = Long.MAX_VALUE;
	static final int START = 1; /* 출발 도시 */
	
	static int N; /* 도시의 수 */
	static int M; /* 노선의 수 */
	
	static List<Bus>[] bus; /* bus[n] : n번째 도시에서 출발하는 모든 노선 */
	static long[] totalCost;

	// 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 N - 1개의 간선을 사용한다.
	static void bellmanFord(int start) {		
		totalCost[start] = 0;
		// N - 1까지 반복문으로 거리 업데이트
		for(int i = 1; i <= N - 1; i++) {
			for(int n = 1; n <= N; n++) {
				for(Bus current : bus[n]) {
					if(totalCost[current.from] != INF) {
						if(totalCost[current.next] > totalCost[current.from] + current.cost) {
							totalCost[current.next] = totalCost[current.from] + current.cost;
						}
					}
				}
			}
		}
		return;
	}
	
	// 음의 사이클 존재 여부를 확인하기 위해 한번 더 M개의 버스 노선을 확인한다.
	static boolean findNegativeCycle() {
		for(int n = 1; n <= N; n++) {
			for(Bus current : bus[n]) {
				if(totalCost[current.next] > totalCost[current.from] + current.cost) {
                    // 업데이트되는 정보가 존재하는 경우
					return true;
				}
			}
		}
		return false;
	}
	
	static void init() {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			int from, next, cost;
			bus = new ArrayList[N + 1];
			for(int i = 1; i <= N; i++) {
				bus[i] = new ArrayList<>();
			}
			totalCost = new long[N + 1];
			Arrays.fill(totalCost, INF);
			
			for(int m = 1; m <= M; m++) {
				st = new StringTokenizer(br.readLine());
				from = Integer.parseInt(st.nextToken());
				next = Integer.parseInt(st.nextToken());
				cost = Integer.parseInt(st.nextToken());
				bus[from].add(new Bus(from, next, cost));
			}
			br.close();
            
			bellmanFord(START);
			
            /* 음수 사이클이 발견되었거나 도시 수가 1인 경우 -1을 return한다 */
			if(findNegativeCycle() || N == 1) {
				bw.append("-1\n");
				bw.flush();
				bw.close();
				return;
			} 
			for(int n = 2; n <= N; n++) {
				if(totalCost[n] == INF) {
					bw.append("-1\n");
				}
				else {
					bw.append(totalCost[n] + "\n");
				}
			}
			bw.flush();
			bw.close();
			return;
		} 
		catch (IOException e) {
			e.printStackTrace();
		}
		return;
	}
	
	public static final void main(String... args) {
		init();
		return;
	}
	
	static class Bus {
		int from;
		int next;
		int cost;
		
		public Bus(int from, int next, int cost) {
			this.from = from;
			this.next = next;
			this.cost = cost;
		}
	}
}

wider93 2년 전 2

findNegativeCycle에서도 inf인 점에서는 갱신을 제외해줘야 합니다.

calgarylof 2년 전 0

와 진짜 감사합니다..

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

문제

문제

출처

ICPC

어디가 문제일까요? 눈 빠지겠어요 ...

calgarylof 2년 전 0

wider93 2년 전 2

calgarylof 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말