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

Benjamin·2023년 3월 18일
백준
0

BAEKJOON

목록 보기
54/70

🙋🏻‍♀️벨만-포드 알고리즘 사용!

Troubleshooting

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

public class Main {
public static ArrayList<tNode> list[];
public static int[] distance;
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());
		M = Integer.parseInt(st.nextToken());
		list = new ArrayList[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<>();
		}
		distance = new int[N+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			makeDirected(A,B,C);
		}
		distance[1]=0;
		boolean isInfinite = bellmanFord(1);
		if(isInfinite) System.out.println("-1");
		else {
			for(int i=2; i<=N; i++) {
				if(distance[i] == Integer.MAX_VALUE) System.out.println("-1");
				else System.out.println(distance[i]);
			}
		}
	}
	public static void makeDirected(int A, int B, int C) {
		list[A].add(new tNode(B,C));
	}
	public static boolean bellmanFord(int v) {
		boolean isInfinite = false;
		for(int i=1; i<=N; i++) {
			for(int k=0; k<list[i].size(); k++) {
				int from = i;
				int to = list[i].get(k).node;
				int time = list[i].get(k).time;
				if(distance[from] == Integer.MAX_VALUE) continue;
				if(distance[to] > distance[from] + time) {
					if(i == N) {
						isInfinite = true;
						return isInfinite;
					}
					distance[to] = distance[from] + time;
				}
			}
		}
		return isInfinite;
	}
}
class tNode {
	int node;
	int time;
	tNode(int node, int time) {
		this.node = node;
		this.time = time;
	}
}

문제

예제의 출력은 다 맞았는데, 틀렸습니다를 받았다.

원인

벨만포드 로직이 문제인것같다.
이렇게 작성하면, 결국 1번 노드부터 N번 노드까지 차례대로 진출간선을 수행하며 거리배열 업데이트하고 끝나버린다.
즉 음수사이클을 검사하는 로직이 없다.

N-1번 수행한 후, 음수사이클 검사를 위해 1번더 수행해서 총 N번 수행한다의 의미는 각 1번의 수행에 모든 간선을 수행하는것이므로, 총 간선수 *N번만큼 수행하는것이다.
나는 바깥 for문에서 N번까지 도니까 된거아닌가?라면 잘못생각했다.

해결

음수사이클을 검사하기위해 이후에 한번더 모든 간선에 대해 반복하도록 수정했다.

Troubleshooting 2

벨만포드를 아래와 같이 수정했다.

public static boolean bellmanFord(int v) {
		boolean isInfinite = false;
		for(int i=1; i<=N; i++) {
			for(int k=0; k<list[i].size(); k++) {
				int from = i;
				int to = list[i].get(k).node;
				int time = list[i].get(k).time;
				if(distance[from] == Integer.MAX_VALUE) continue;
				if(distance[to] > distance[from] + time) {
					distance[to] = distance[from] + time;
				}
			}
		}
		for(int i=1; i<=N; i++) {
			for(int k=0; k<list[i].size(); k++) {
				int from = i;
				int to = list[i].get(k).node;
				int time = list[i].get(k).time;
				if(distance[from] == Integer.MAX_VALUE) continue;
				if(distance[to] > distance[from] + time) {
					isInfinite = true;
					return isInfinite;
				}
			}
		}
		return isInfinite;
	}

문제

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

원인

이건 문제가 아니었다.

우선 i 한번씩마다 모든 간선에 대해서 반복해야한다. 따라서 리스트배열로 선언하면 안된다.

하지만 위와같이 작성하면 1번 노드에서 나가는 간선만 다 검사하고, 그 다음에 2번 노드에서 나가는 간선만 다 검사하고,... N번노드까지 각 간선이 한번씩만 수행되기때문에, 노드 번호에 따라서 아직 방문하지 않았던 노드라고 판별되어 해당 노드의 진출간선은 수행되지않을수도 있기 때문이다.

해결

모든 간선은 한 번씩 수행되어야하기때문에, list를 리스트배열에서 리스트로 변경했다.

Troubleshooting 3

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

public class Main {
public static ArrayList<tNode> list = new ArrayList<>();
public static int[] distance;
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());
		M = Integer.parseInt(st.nextToken());
		distance = new int[N+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			makeDirected(A,B,C);
		}
		
		distance[1]=0;
		boolean isInfinite = bellmanFord(1);
		if(isInfinite) System.out.println("-1");
		else {
			for(int i=2; i<=N; i++) {
				if(distance[i] == Integer.MAX_VALUE) System.out.println("-1");
				else System.out.println(distance[i]);
			}
		}
	}
	public static void makeDirected(int A, int B, int C) {
		list.add(new tNode(A,B,C));
	}
	public static boolean bellmanFord(int v) {
		boolean isInfinite = false;
		for(int i=1; i<=N; i++) {
			for(int k=0; k<list.size(); k++) {
				int from = list.get(k).start;
				int to = list.get(k).end;
				int time = list.get(k).time;
				if(distance[from] == Integer.MAX_VALUE) continue;
				if(distance[to] > distance[from] + time) {
					if(i==N) {
						isInfinite = true;
						return isInfinite;
					}
					distance[to] = distance[from] + time;
				}
			}
		}
		return isInfinite;
	}
}
class tNode {
	int start;
	int end;
	int time;
	tNode(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}

문제

출력초과가 났다.

원인

도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이고, C의 범위는 -10,000 ≤ C ≤ 10,000이므로, 최악의경우에 최대 300만번의 반복문을 돌게 된다.
이때 음의 간선이 -10,000 이라면, 약 -300억의 값으로 underflow가 발생하게 되어 출력초과가 나오는 경우가 발생한다. (양의 간선 10,000의 경우도 마찬가지이다)

해결

따라서 이 범위를 다 수용할 수 있도록, distance배열의 타입을 int에서 long 으로 수정했다.

제출 코드

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

public class Main {
public static ArrayList<tNode> list = new ArrayList<>();
public static long[] distance;
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());
		M = Integer.parseInt(st.nextToken());
		distance = new long[N+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			makeDirected(A,B,C);
		}
		
		distance[1]=0;
		boolean isInfinite = bellmanFord(1);
		if(isInfinite) bw.write("-1");
		else {
			for(int i=2; i<=N; i++) {
				if(distance[i] == Integer.MAX_VALUE) bw.write("-1 \n"); 
				else bw.write(distance[i]+ "\n");
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
	public static void makeDirected(int A, int B, int C) {
		list.add(new tNode(A,B,C));
	}
	public static boolean bellmanFord(int v) {
		boolean isInfinite = false;
		for(int i=1; i<=N; i++) {
			for(int k=0; k<list.size(); k++) {
				int from = list.get(k).start;
				int to = list.get(k).end;
				int time = list.get(k).time;
				if(distance[from] == Integer.MAX_VALUE) continue;
				if(distance[to] > distance[from] + time) {
					if(i==N) {
						isInfinite = true;
						return isInfinite;
					}
					distance[to] = distance[from] + time;
				}
			}
		}
		return isInfinite;
	}
}
class tNode {
	int start;
	int end;
	int time;
	tNode(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}

주의할 점

  • 벨만-포드는 리스트정보를 리스트배열이 아닌 리스트로 선언하는게 좋다!
    -> 간선 개수만큼 반복하는것을 N번동안 하기위해

  • 거리배열이 누적될 때, 최악의 경우에 int타입이 수용가능한지 확인하자!(출력초과가나서 당황했다)
    -> 왠만하면 정수타입은 long타입으로하는 습관을 들이자.

  • 실제로 수행할 때는 에지가 저장된 순서에 따라 동작하므로 이론의 업데이트와는 약간 다르지만, 알고리즘에 영향을 미치지는 않는다.

profile
Benjamin
이전 포스트

[백준] 1854 : K번째 최단경로 찾기 - JAVA

다음 포스트

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

0개의 댓글