# BOJ01504 특정한 최단 경로
https://www.acmicpc.net/problem/1504 (opens new window)
방향성이 없는 그래프가 주어진다. 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 하지만 이때 두 가지 조건을 만족해야 한다.
WARNING
임의로 주어진 두 정점을 반드시 통과해야 한다.
또한 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능하다. 하지만 매 정점 마다 항상 최단 경로를 이용해야 한다.
최단 경로 알고리즘을 아주 약간 응용한 문제이다.
# dijkstra 메소드
이번 dijkstra메소드는 start, end 정점이 주어지면 현재 시점에서 가장 짧은 최단 경로의 값을 반환해주어야 한다.
또한 한번 이동했던 정점, 간선을 다시 이동할 수 있다. 그렇기 때문에 매번 최단 경로를 저장하기 위한 배열을 초기화해야 한다.
d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE);
마지막 값은 end의 정점까지 걸리는 최단 경로를 반환해야 한다. 만약 end로 가기 위한 최단 경로가 없다면 음수의 값을 반환하여 처리한다.
dijkstra는 음수의 경로를 가질 수 없기 때문에 임의로 불안정한 값임을 알려준다.
물론 그대로 INF를 반환해도 되지만 INF의 경우 Integer.MAX_VALUE이기 때문에 최단 경로를 더하는 과정에서 의도하지 않은 값으로 처리될 가능성이 있다.
if (d[end] == INF) {
return -1;
} else {
return d[end];
}
dijkstra 메소드의 최종 코드이다.
private static int dijkstra(int start, int end) {
d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE);
PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
if (o1.distance < o2.distance) {
return -1;
} else if (o1.distance == o2.distance) {
return 0;
}
return 1;
});
d[start] = 0;
priorityQueue.add(new Node(start, 0));
while (!priorityQueue.isEmpty()) {
Node node = priorityQueue.poll();
int index = node.index;
int distance = node.distance;
if (d[index] < distance) {
continue;
}
for (int i = 0; i < graph.get(index).size(); i++) {
int cost = d[index] + graph.get(index).get(i).distance;
if (cost < d[graph.get(index).get(i).index]) {
d[graph.get(index).get(i).index] = cost;
priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
}
}
}
if (d[end] == INF) {
return -1;
} else {
return d[end];
}
}
# 최종 코드
방향이 없는 그래프이기 때문에 양방향으로 그래프를 세팅해준다.
for (int i = 0; i < e; i++) {
int a = scanner.nextInt(); // start
int b = scanner.nextInt(); // end
int c = scanner.nextInt(); // weight
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
거의 대부분의 코드가 최단 경로와 비슷하지만 주의해야 할 부분이 있다. 세준이는 임의로 주어진 두 정점을 반드시 통과해야 한다.
int v1 = scanner.nextInt(); // 필수 정점
int v2 = scanner.nextInt(); // 필수 정점
이제 위에서 입력받은 정점을 반드시 통과하는 경우는 총 두 가지이다. 각각의 경우에 맞는 최단 경로를 합산한다.
long answer1 = 0;
answer1 += dijkstra(1, v1);
answer1 += dijkstra(v1, v2);
answer1 += dijkstra(v2, n);
long answer2 = 0;
answer2 += dijkstra(1, v2);
answer2 += dijkstra(v2, v1);
answer2 += dijkstra(v1, n);
각각의 최단 경로가 없는 경우 -1를 반환하도록 하였다. 합산한 값 둘 중 작은 값이 0보다 작은 경우 정상적으로 이어지지 않은 경로이므로 -1을 반환한다.
최단 경로가 정상적으로 확인되면 합산 중 더 작은 경로를 찾아 반환한다.
if (Math.min(answer1, answer2) < 0) {
System.out.println(-1);
} else {
System.out.println(Math.min(answer1, answer2));
}
최종 제출 코드이다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ1504 {
public static final int INF = Integer.MAX_VALUE;
private static int n, e;
private static List<List<Node>> graph = new ArrayList<>();
private static int[] d;
private static class Node {
private final int index;
private final int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
}
private static int dijkstra(int start, int end) {
d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE);
PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
if (o1.distance < o2.distance) {
return -1;
} else if (o1.distance == o2.distance) {
return 0;
}
return 1;
});
d[start] = 0;
priorityQueue.add(new Node(start, 0));
while (!priorityQueue.isEmpty()) {
Node node = priorityQueue.poll();
int index = node.index;
int distance = node.distance;
if (d[index] < distance) {
continue;
}
for (int i = 0; i < graph.get(index).size(); i++) {
int cost = d[index] + graph.get(index).get(i).distance;
if (cost < d[graph.get(index).get(i).index]) {
d[graph.get(index).get(i).index] = cost;
priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
}
}
}
if (d[end] == INF) {
return -1;
} else {
return d[end];
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt(); // 정점의 개수
e = scanner.nextInt(); // 간선의 개수
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < e; i++) {
int a = scanner.nextInt(); // start
int b = scanner.nextInt(); // end
int c = scanner.nextInt(); // weight
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
int v1 = scanner.nextInt(); // 필수 정점
int v2 = scanner.nextInt(); // 필수 정점
long answer1 = 0;
answer1 += dijkstra(1, v1);
answer1 += dijkstra(v1, v2);
answer1 += dijkstra(v2, n);
long answer2 = 0;
answer2 += dijkstra(1, v2);
answer2 += dijkstra(v2, v1);
answer2 += dijkstra(v1, n);
if (Math.min(answer1, answer2) < 0) {
System.out.println(-1);
} else {
System.out.println(Math.min(answer1, answer2));
}
}
}
# 주의할 점
long answer1 = 0;
answer1 += dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
long answer1 = 0;
answer1 += dijkstra(1, v1);
answer1 += dijkstra(v1, v2);
answer1 += dijkstra(v2, n);
위 두 코드는 언듯 보면 동일한 값을 answer에 저장하는 것 처럼 보인다. 하지만 dijkstra가 Integer.MAX_VALUE를 반환하게 되면 전혀 다른 결과를 확인할 수 있다.
dijkstra의 반환 타입은 int이다. int는 최대 0x7fffffff을 가질 수 있다. 여기서 1을 더하게 되면 int가 가질 수 있는 가장 작은 값을 가지게 된다.
int a = Integer.MAX_VALUE + 1;
System.out.print(a); // -2147483648
long answer1 = 0;
answer1 += dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
위 코드의 경우 dijkstra가 하나라도 Integer.MAX_VALUE를 그대로 반환했다고 가정해보면 다른 값들 중 양수가 하나라도 존재하게 될 경우 의도치 않게 음수의 값이 answer1에 저장될 것이다.
answer1은 long 타입이지만 dijkstra는 모두 int 값을 반환하기 때문에 (int) + (int) + (int)의 형태로 우선 연산을 진행하고 난 후 최종값을 answer1에 저장한다.
long answer1 = 0;
answer1 += dijkstra(1, v1);
answer1 += dijkstra(v1, v2);
answer1 += dijkstra(v2, n);
위 코드는 매번 계산한 dijkstra를 answer1에 저장하기 때문에 int의 표현 범위를 넘어가도 long 타입은 더 큰 표현 범위를 가지고 있기 때문에 의도대로 answer1에 합산한 값이 저장된다.
위에서 작성한 dijkstra는 적절한 경로를 찾기 못하면 -1로 반환할 수 있도록 설정한 이유는 위와 같은 상황을 사전에 방지하기 위함이다.