백준 1219번 자바 ☆

1. 문제

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

1219번: 오민식의 고민

 

2. 접근 방식

기본적인 접근 방식은 벨만포드를 이용해서 푼다.

하지만 음의 사이클이 아닌 양의 사이클이라는 점과 시작 노드가 사이클에 속한 노드일 경우 도착 노드 또한 사이클에 속한것으로 봐야한다.

 

마지막으로 가장 중요한 부분은 양수 사이클이 존재할 때 시작 -> 도착 노드의 경로에 사이클이 존재 하지 않을 경우에 대한 예외 처리이다. 

첫 번째 방법은 벨만포드 기본적인 탐색 횟수인 N-1회를 N의 값의 범위만큼 충분히 늘려 주는 것이고

두 번째 방법은 사이클이 발생한 노드를 따로 저장하는 방법이다. 

 

내 코드는 첫 번째 방법을 따랐고,

두 번째 방법은 

https://steady-coding.tistory.com/93

여기를 참고하자.

3. 구현

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

public class Main1219 {

	static int N,M,start,end;
	static long[] money;
	static int[] getMoney;
	static Edge[] edges;
	
	static class Edge {
		int start,end,val;
		public Edge(int start, int end, int val) {
			this.start = start;
			this.end = end;
			this.val = val;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		money = new long[N];
		getMoney = new int[N];
		edges = new Edge[M];
		
		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 cost = Integer.parseInt(st.nextToken());
			edges[i] = new Edge(start, end, cost);
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			getMoney[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(money, Long.MIN_VALUE);
		money[start] = getMoney[start];
		
		bellmanFord();
		if (money[end] == Long.MIN_VALUE) {
			System.out.println("gg");
			return;
		}
		if (money[end] == Long.MAX_VALUE) {
			System.out.println("Gee");
			return;
		}
		System.out.println(money[end]);
		
	}
	
	public static void bellmanFord() {
		for (int i=0; i<=N+50; i++) {
			for (int j=0; j<M; j++) {
				Edge edge = edges[j];
				if (money[edge.start] == Long.MIN_VALUE) {
					continue;
				}
				if (money[edge.start] == Long.MAX_VALUE) {
					money[edge.end] = Long.MAX_VALUE;
					continue;
				}
				if (money[edge.end] < money[edge.start] + getMoney[edge.end] - edge.val) {
					money[edge.end] = money[edge.start] + getMoney[edge.end] - edge.val;
					if (i >= N-1) {
						money[edge.end] = Long.MAX_VALUE; 
					}
				}
			}
		}
	}
}

 

4. 정리