[백준] 1219 : 오민식의 고민 - JAVA

Benjamin·2023년 3월 18일
백준
0

BAEKJOON

목록 보기
55/71

🙋 벨만-포드 알고리즘 사용!

Troubleshooting

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

public class Main{
	public static ArrayList<sNode> list;
	public static long[] distance;
	public static int[] availableMoney;
	public static int N,M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int here = Integer.parseInt(st.nextToken());
		int goal = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		distance = new long[N];
		availableMoney = new int[N];
		list = 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 value =Integer.parseInt(st.nextToken());
			list.add(new sNode(start,end,value));
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			availableMoney[i] = Integer.parseInt(st.nextToken());
			distance[i] = Long.MIN_VALUE;
		}
		distance[here] = availableMoney[here];
		bellanFord(here);
		if(distance[goal] == Long.MIN_VALUE) System.out.println("gg");
		else if(distance[goal] == Long.MAX_VALUE) System.out.println("Gee");
		else System.out.println(distance[goal]);
	}
	
	public static void bellanFord(int v) {
		for(int i=1; i<=N+100; i++) {
			for(int j=0; j<list.size(); j++) {
				int start = list.get(j).start;
				int end = list.get(j).end;
				int value = list.get(j).value;
				if(distance[start] != Long.MIN_VALUE && (distance[end] < distance[start] - value + availableMoney[end])) {
					if(i >= N) {
						distance[end] = Long.MAX_VALUE;
					}
					else distance[end] = distance[start] - value + availableMoney[end];
				}

			}
		}
	}
}

class sNode{
	int start,end,value;
	
	public sNode(int start, int end, int value) {
		this.start = start;
		this.end = end;
		this.value = value;
	}
}

문제

틀렸습니다를 받았다.

원인

에지를 체크할 때 시작 노드가 양의 사이클에 속하면, 도착 노드도 양의 사이클에 속하도록 해야한다. (무수히 많이 반복되면, 양의사이클이 결국 영향을 미치기때문이다)

해결

값을 업데이트하는 수식으로 검사하기 전에 if(distance[start] == Long.MAX_VALUE) distance[end] = Long.MAX_VALUE;코드를 추가했다.
(Long.MAX_VALUE = 가장 큰 값이므로 양의 사이클에 속한다는 의미이다)

Troubleshooting 2

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

public class Main {
	public static ArrayList<sNode> list;
	public static long[] distance;
	public static int[] availableMoney;
	public static int N,M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int here = Integer.parseInt(st.nextToken());
		int goal = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		distance = new long[N];
		availableMoney = new int[N];
		list = 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 value =Integer.parseInt(st.nextToken());
			list.add(new sNode(start,end,value));
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			availableMoney[i] = Integer.parseInt(st.nextToken());
			distance[i] = Long.MIN_VALUE;
		}
		distance[here] = availableMoney[here];
		bellanFord(here);
		if(distance[goal] == Long.MIN_VALUE) System.out.println("gg");
		else if(distance[goal] == Long.MAX_VALUE) System.out.println("Gee");
		else System.out.println(distance[goal]);
	}
	
	public static void bellanFord(int v) {
		for(int i=1; i<=N+50; i++) {
			for(int j=0; j<list.size(); j++) {
				int start = list.get(j).start;
				int end = list.get(j).end;
				int value = list.get(j).value;
				if(distance[start] == Long.MAX_VALUE) distance[end] = Long.MAX_VALUE;
				else if(distance[start] != Long.MIN_VALUE && (distance[end] < distance[start] - value + availableMoney[end])) {
					if(i >= N) {
						distance[end] = Long.MAX_VALUE;
					}
					else distance[end] = distance[start] - value + availableMoney[end];
				} 
			}
		}
	}
}

class sNode{
	int start,end,value;
	
	public sNode(int start, int end, int value) {
		this.start = start;
		this.end = end;
		this.value = value;
	}
}

문제

여전히 틀렸습니다를 받았다.

원인

N,M이 전역변수, 지역변수로 둘 다 선언하고있었는데 모르고있었다.
그래서 0으로 되어있는 전역변수를 기준으로 벨만포드 반복문이 실행되고있었던것이다.

해결

main함수에서 N,M 앞에 타입 int를 지웠다.

어이없는 실수... 조심하자 !

제출코드

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

public class Main {
	public static ArrayList<sNode> list;
	public static long[] distance;
	public static int[] availableMoney;
	public static int N,M;
	public static void main(String[] args) throws IOException {
		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());
		int here = Integer.parseInt(st.nextToken());
		int goal = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		distance = new long[N];
		availableMoney = new int[N];
		list = 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 value =Integer.parseInt(st.nextToken());
			list.add(new sNode(start,end,value));
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			availableMoney[i] = Integer.parseInt(st.nextToken());
			distance[i] = Long.MIN_VALUE;
		}
		distance[here] = availableMoney[here];
		bellanFord(here);
		if(distance[goal] == Long.MIN_VALUE) System.out.println("gg");
		else if(distance[goal] == Long.MAX_VALUE) System.out.println("Gee");
		else System.out.println(distance[goal]);
	}
	
	public static void bellanFord(int v) {
		for(int i=1; i<=N+50; i++) { //N+50 대신 2*N도 가능하다. -> N+50 인 이유는 N의 최대값이 50이기때문에 설정했다. 
			for(int j=0; j<list.size(); j++) {
				int start = list.get(j).start;
				int end = list.get(j).end;
				int value = list.get(j).value;
				if(distance[start] == Long.MAX_VALUE) distance[end] = Long.MAX_VALUE;
				else if(distance[start] != Long.MIN_VALUE && (distance[end] < distance[start] - value + availableMoney[end])) {
					if(i >= N) {
						distance[end] = Long.MAX_VALUE;
					}
					else distance[end] = distance[start] - value + availableMoney[end];
				} 
			}
		}
	}
}

class sNode{
	int start,end,value;
	
	public sNode(int start, int end, int value) {
		this.start = start;
		this.end = end;
		this.value = value;
	}
}

주의할 점

  • 처음에 벨만포드 시작하는 노드의 거리(버는금액)를 초기화 할때, 이전 벨만포드처럼 0으로 초기화하는게아니라 distance[here] = availableMoney[here];와 같이 주어진 비용으로 초기화해야한다.

  • 초기 distance의 모든값을 0으로 초기화하는게 아닌, 가장 작은 값인 Long.MIN_VALUE;으로 초기화해야한다. (최대값을 찾는것이기때문에)

  • 에지의 출발 노드가 양의사이클에 속하면, 도착노드도 양의사이클에 속하도록 해야한다.

  • 충분한 edge relaxation을 통해 사이클의 존재 여부, 해당 사이클이 도착 지점까지 영향을 미치는지 추가 relaxation이 필요하다.
    여기선 N 최대값이 50이므로 N+50번 수행한다.
    edge relaxation N-1회부턴 만약 positive cycle이 발견되면 해당 노드의 값을 아주 큰 값으로 설정한다. (나는 Long.MIN_VALUE라고 했음)
    이전 노드가 Long.MIN_VALUE면 다음 노드도 Long.MIN_VALUE이다.

궁금한 점

주석으로 표시해둔 벨만포드함수의 바깥쪽 반복문 조건문에 의문이있다.

보통 다 풀이를 보면, 노드의 수만큼 +해줘서 한다.(그래서 현재 문제기준으로는 N의 최대가 50이기때문에 for(int i=1; i<=N+50; i++)해도 맞긴하다.

근데 쓸데없는 반복을 줄이기위해 그때그때 N값에 따라 필요한만큼만 늘려보려고했다.

이해가 안가는건, i<=2*(N-1)이 안된다. i<=2*N은 되고..

그런데 이론적으로 N-1번 반복하는게 모든 에지를 반복하기위한 횟수이니까, 후에 또 N-1번 반복하면 결국 모든 에지를 2번씩 반복하는거니까 양의 사이클이 어디까지 영향을미치는지 알 수 있지않나?

왜 2*(N-1)번만 하는건 틀렸다고 뜨는지 모르겠다.
-> 백준에 질문올려둔 상태

profile
Benjamin
이전 포스트

[백준] 11657 : 타임머신 - JAVA

다음 포스트

[백준] 1865 : 웜홀 - JAVA

1개의 댓글

comment-user-thumbnail
4riend
2023년 7월 25일

0번 노드부터 사용이 되기 때문에 n * 2가 맞을 것 같아요!

가장 바깥 반복문이 노드수 * 2가 되는 이유는 가장 큰 사이클을 염두해서 정한 것 같아요.

N의 크기를 갖는 가장 큰 사이클이 있다면 다시 한 번 더 순환하는데 2*N 만큼 걸리기 때문..?

저도 방금 풀면서 혼자 이해한 거라 틀릴 수도 있습니다!!

답글 달기