[Baekjoon] 1865_웜홀

Gold III

문제(출처: https://www.acmicpc.net/problem/1865)

---

< 웜홀 >

 

문제 풀이 

 

벨만-포드 알고리즘을 사용해서 해결했다.

 

처음에는 데이크스트라를 사용해서 문제를 해결할 수 있는지 알았지만 음수 가중치가 있을 경우 벨만-포드 알고리즘을 사용한다는 것을 알게 되었다. 데이크스트라를 사용해서 문제를 해결할 수 없나 찾아보니 음수 가중치가 있다고 해서 데이크스트라를 사용할 수 없는 것이 아니라 사이클 형성 여부에 따라 사용 여부가 갈리는 것이라고 알게 되었다.

 

 

 my solution (Java)

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.StringTokenizer;

public class _1865_ { // 웜홀
	static class Edge {
		private int start;
		private int end;
		private int d;

		public Edge(int start, int end, int d) {
			this.start = start;
			this.end = end;
			this.d = d;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		ArrayList<Edge> list = new ArrayList<>();
		int result[];
		boolean visited[];
		boolean flag = false;

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(bf.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			result = new int[n + 1];
			visited = new boolean[n + 1];
			flag = false;

			for (int j = 0; j < m; j++) {
				st = new StringTokenizer(bf.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				list.add(new Edge(s, e, d));
				list.add(new Edge(e, s, d));
			}

			for (int j = 0; j < w; j++) {
				st = new StringTokenizer(bf.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				list.add(new Edge(s, e, -d));
			}

			for (int j = 1; j <= n; j++) {
				if (visited[j]) {
					continue;
				}
				for (int k = 1; k <= n; k++) {
					result[k] = Integer.MAX_VALUE;
				}
				visited[j] = true;
				result[j] = 0;

				for (int k = 0; k < n; k++) {
					for (int v = 0; v < list.size(); v++) {
						Edge edge = list.get(v);
						if (result[edge.start] != Integer.MAX_VALUE && result[edge.end] > result[edge.start] + edge.d) {
							result[edge.end] = result[edge.start] + edge.d;
							visited[edge.end] = true;
							if (k == n - 1) {
								flag = true;
								break;
							}
						}
					}
					if (flag) {
						break;
					}
				}
				if (flag) {
					break;
				}
			}
			if (flag) {
				bw.write("YES\n");
			} else {
				bw.write("NO\n");
			}
			list.clear();
		}
		bw.flush();
	}
}

변수)
Edge : 시작 지점, 도착 지점, 시간
t : 테스트 케이스 개수
list : 그래프
result : 이동하는 데 걸리는 시간
visited : 방문 여부
flag : 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능한지 여부
n, m, w : 지점의 수, 도로의 개수, 웜홀의 개수
s, e, d : 시작 지점, 도착 지점, 줄어드는 시간

 

Edge

시작 지점, 도착 지점, 시간을 변수로 가짐

 

Main

테스트 케이스 수만큼 아래 과정을 반복한다.

 

지점의 수, 도로의 개수, 웜홀의 개수를 입력받는다. 도로의 개수만큼 도로의 정보를 입력받아 양방향으로 저장한다. 웜홀의 개수만큼 웜홀의 정보를 입력받아 단방향으로 저장한다. 출발 지점이 정해져 있지 않으므로 모든 지점에서 시작하기 위해 지점의 수만큼 반복한다. 만약 이미 방문했던 곳이라면 다음 지점을 탐색한다. 최단 시간을 구하기 위해 먼저 각 지점의 시간을 Integer.MAX_VALUE로 초기화한다. 시작 지점의 시간을 0으로 저장한다. 지점의 수만큼 모든 도로와 웜홀을 탐색해 보며 값이 업데이트되는지 확인한다. 만약 값이 업데이트될 때가 (지점의 수-1) 번째 라면 음수 사이클이 발생한 것이므로 종료한다.

 

음수 사이클이 발생했다면 YES를, 그렇지 않다면 NO를 출력한다.

---

---