공부 기록

가능한 경로 2가지

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

다익스트라 알고리즘을 시작점 1, v1, v2로 하여 각각 구한뒤 더했을 때 최솟값을 구하도록 한다

import java.util.*;

public class Main {
	public static long MAX = 800 * 200000 * 1000 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
			mat[end][start] = Math.min(mat[end][start], weight);
		}

		int v1 = in.nextInt();
		int v2 = in.nextInt();

		long distFrom1[] = dijkstra(1, n, mat);
		long distFromV1[] = dijkstra(v1, n, mat);
		long distFromV2[] = dijkstra(v2, n, mat);

		long ans = -1;
		// 갈 수 없는 경우 체크
		if (distFrom1[v1] < MAX && distFromV1[v2] < MAX && distFromV2[n] < MAX) {
			ans = distFrom1[v1] + distFromV1[v2] + distFromV2[n];
		}
		if (distFrom1[v2] < MAX && distFromV2[v1] < MAX && distFromV1[n] < MAX) {
			ans = Math.min(ans, distFrom1[v2] + distFromV2[v1] + distFromV1[n]);
		}
		System.out.println(ans);
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}
		
		return dist;
	}
}

2020/07/07 - [알고리즘 공부] - boj 1916: 최소비용 구하기

위의 풀이와 똑같지만, 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력하기 위해서는

경로의 최솟값이 업데이트 될 때의 위치를 저장하도록 하면 된다.

마지막에 답을 구할 때에는 이전 위치를 저장하도록 했으므로

도착지점->시작지점 순으로 스택에 넣고 빼면서 프린트 한다.

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		int route[] = new int[n + 1];
		Arrays.fill(route, start);
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		route[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}
			if (index == -1) {
				break;
			}
			isVisited[index] = true;
			
			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
					route[j] = index;
				}
			}

		}
		
		System.out.println(dist[end]);
		Stack<Integer> answerSet=new Stack<Integer>();
		int now=end;
		while(true) {
			if(now==start) {
				answerSet.add(now);
				break;
			}
			
			answerSet.add(now);
			now=route[now];
		}
		
		System.out.println(answerSet.size());
		while(!answerSet.isEmpty()) {
			System.out.print(answerSet.pop()+" ");
		}
	}
}

• 최단경로를 구하는 알고리즘
  • 다익스트라 알고리즘: 모든 간선에 대해 1번만 검사
  • 모든 정점을 선택(V-1)하고, isVisited==false인 값 중에서 가장 가까운 값을 선택하는데 걸리는 시간은 O(V): 총 O(V^2)
  • 음수가 있을 때 사용할 수 없다
  • 정점을 처리했는지 안했는지 체크해야한다 (isVisited)

c.f. 벨만 포드 알고리즘: 식을 N-1번 검사, 음수가 있을 때 사용 가능

맨 처음 풀이에서 isVisited==false인 값 중 가장 가까운 값을 선택할 때

min=MAX로 초기화 하고 min을 업데이트 해 나갔을 때에는 런타임 에러가 발생했다.

그래서 index가 업데이트 되지 않을 때 런타임 에러가 발생하므로 index==-1인 경우 따로 break문을 추가했다.

이 외에도 min=MAX+1으로 설정하면 break문 없이 정답이 나온다.

처음에는 Integer.MAX_VALUE로 MAX를 설정했는데, 오버플로우 등이 일어나서

비용 범위가 100000까지고 노드가 최대 1000개이므로 최대 INF를 1000000000로 잡았다.

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}
			if(index==-1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
				}
			}

		}
		System.out.println(dist[end]);
	}
}

유사한 문제

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;
	}
}