공부 기록

유사한 문제

2020/07/06 - [알고리즘 공부] - boj 11657: 타임머신

음수 사이클의 존재 여부를 찾는 문제이다.

주의할 점은 사이클이 웜홀을 포함하는지 여부이기 때문에 웜홀의 start가 시작점일때를 체크하도록 한다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 0; t < testcase; t++) {

			int n = in.nextInt();
			int m = in.nextInt();
			int w = in.nextInt();

			List<Hole> holes = new ArrayList<Hole>();

			for (int i = 0; i < m; i++) {
				int start = in.nextInt();
				int end = in.nextInt();
				int time = in.nextInt();
				holes.add(new Hole(start, end, time));
				holes.add(new Hole(end, start, time));
			}

			HashSet<Integer> startSets = new HashSet<Integer>();
			for (int i = 0; i < w; i++) {
				int start = in.nextInt();
				int end = in.nextInt();
				int time = in.nextInt();
				startSets.add(start);
				holes.add(new Hole(start, end, -time));
			}

			boolean isNegativeCycle = false;
			Iterator it = startSets.iterator();
			while (it.hasNext()) {
				long dist[] = new long[n + 1];
				Arrays.fill(dist, Long.MAX_VALUE);
				dist[(int) it.next()] = 0;

				for (int i = 1; i <= n; i++) {
					for (int j = 0; j < holes.size(); j++) {
						int start = holes.get(j).start;
						int end = holes.get(j).end;
						int time = holes.get(j).time;

						if (dist[start] != Long.MAX_VALUE && dist[end] > dist[start] + time) {
							dist[end] = dist[start] + time;
							if (i == n) {
								isNegativeCycle = true;
							}
						}
					}
				}
				if (isNegativeCycle) {
					break;
				}
			}
			if (isNegativeCycle) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}

class Hole {
	int start, end, time;

	public Hole(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}

• 벨만 포드 알고리즘: 정점 개수가 V개일 때, 최단 경로는 최대 V-1 개의 간선으로 이루어져 있다.
  • 가중치가 음수인 경우도 사용 가능하다
  • 시작점이 1개이다
  • 음수 사이클을 검사할 수 있다
  • 시간복잡도 O(VE)
  • E <= V^2 이므로 시간복잡도는 O(V^3)
  • 벨만 포드 알고리즘에선 인접 행렬/인접 리스트가 필요 없다. - 인접 행렬/인접 리스트는 어떤 정점과 연결되어 있는 간선을 효율적으로 탐색하는 것인데, 벨만 포드 알고리즘은 모든 정점/간선을 모두 검사한다. 따라서 효율적인 자료구조가 필요 없음 

c.f. 다익스트라 알고리즘: 가중치가 음수인 경우는 사용할 수 없다.

이 문제에서 음수 사이클이 존재하는 경우 해당 도시로 가는 시간을 무한히 되돌릴 수 있다.

최단 경로는 최대 V-1개의 간선으로 이루어져있다고 했으니까 V-1단계까지 벨만 포드 알고리즘을 적용하면 최단 경로가 나올 것이다.

이 때, 음수 사이클을 찾는 방법은 한 단계를 더 했을 때(i=n), 최단 경로가 변경된다. = 최단 경로가 존재하지 않는다.

즉 아래 코드에서 최단 경로가 변경됐는데 i=n일 때 음수사이클 존재를 확인한다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		List<Bus> buses = new ArrayList<Bus>();
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();
			buses.add(new Bus(start, end, time));
		}
		long dist[] = new long[n + 1];
		Arrays.fill(dist, Long.MAX_VALUE);
		dist[1] = 0;
		boolean isNegativeCycle = false;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < m; j++) {
				int start = buses.get(j).start;
				int end = buses.get(j).end;
				int time = buses.get(j).time;
				if (dist[start] != Long.MAX_VALUE && dist[end] > dist[start] + time) {
					dist[end] = dist[start] + time;
					if (i == n) {
						isNegativeCycle = true;
					}
				}
			}
		}
		if (isNegativeCycle) {
			System.out.println("-1");
		} else {
			for (int i = 2; i <= n; i++) {
				if (dist[i] == Long.MAX_VALUE) {
					System.out.println("-1");
				} else {
					System.out.println(dist[i]);
				}
			}
		}
	}
}
class Bus {
	int start, end, time;
	public Bus(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}