[백준 1504 자바] - 특정한 최단경로 #dijkstra
문제리뷰
해당 문제는 문제 제목에서 알 수 있듯 "최단경로"를 구하는 문제이다. 또한, Input Size (노드개수, 엣지개수)에 따라 시간복잡도에 맞는 최단경로 알고리즘을 분류해낼 수 있는가?를 의도한 문제인 것 같다. 다익스트라와 플로이드-워셜과 같은 최단경로 알고리즘을 복기할 필요성을 느낀 문제이다.
풀이
시간복잡도 분석
- 2 <= 노드의 개수:N <= 800
- 0 <= 간선의 개수:E <= 200,000
- Worst Case: 노드의 개수가 800개이고, 간선의 개수가 20만개인 그래프
- O(N*E) 불가, O(N^3) 불가
유형 분석
- 그래프탐색 (최단경로)
- 플로이드-워셜 불가 (∵ O(N^3))
- 다익스트라 가능 (∵ O(E logV), 모든 가중치가 양수)
설계
이슈1: "임의로 주어진 두 정점 v1, v2는 반드시 통과"
이슈2: 시간복잡도
문제의 조건에 추가사항이 있다. "임의로 주어진 두 정점 v1, v2는 반드시 통과"해야 한다는 점이다.
플로이드-워셜
플로이드-워셜 알고리즘의 경우 "모든 노드" -> "모든 노드"에 대한 최단거리를 구할 수 있다. 따라서 idx에 해당하는 노드 사이의 최단거리를 나타내는 이차원 배열을 dp라고 선언했을 때, min (dp[1][v1] + dp[v1][v2] + dp[v2][N] , dp[1][v2] + dp[v2][v1] + dp[v1][N])으로 목표로하는 최단경로를 구할 수 있을 것이다. 하지만, 여기서 추가적으로 시간복잡도에 대한 고려를 해봐야 한다. 플로이드-워셜 알고리즘의 경우 O(N^3)만큼 소요되므로, Worst Case는 O(800^3)으로써 시간복잡도가 초과하게 된다.
다익스트라
다익스트라의 경우 "특정 노드" -> "모든 노드"에 대한 최단거리를 구할 수 있고, 시간복잡도는 O(E logV)이다. 따라서, 시작노드 -> v1 -> v2 -> N 과 시작노드 -> v2 -> v1 -> N의 최단거리 중 최솟값을 구하면 시간복잡도도 초과하지 않고 목표로하는 값을 구할 수 있다. 단, 여기서 다익스트라를 dijkstra(시작노드), dijkstra(v1), dijkstra(v2) 총 3번 돌려줘야 한다. 앞에서 언급한 바와 같이, 다익스트라는 "특정 노드" -> "모든 노드"에 대한 최단거리만을 구할 수 있기 때문이다.
여기서 주의해야할 점은, 단순히 min(1번노드 -> v1, 1번노드 -> v2) 로만 접근하면 반례가 존재한다.
- 반례:
- 1번 -> v1(w10) -> v2(w:20) -> N(w:100000)
- 1번 -> v2(w100) -> v1(w:20) -> N(w:1)
- 반례와 같이 결국, min (시작노드 -> v1 최소경로 + v1->v2 최소경로 + v2 -> N 최소경로 , 시작노드 -> v2최소경로 + v2->v1최소경로 + v1->N 최소경로)로 접근해야한다.
해당 문제는, 다익스트라에 대한 이해가 없으면 해결하기 힘든 문제이니 다익스트라에 대한 포스팅글을 참고하면 좋을 것이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int N, E; //노드, 엣지 개수
static List<Node>[] adj;
static int[] minWeight;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
adj = new ArrayList[N+1];
minWeight = new int[N+1];
for(int i=1; i<=N; i++) {
adj[i] = new ArrayList<>();
}
for(int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int nodeA = Integer.parseInt(st.nextToken());
int nodeB = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adj[nodeA].add(new Node(nodeB, weight));
adj[nodeB].add(new Node(nodeA, weight));
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
dijkstra(1);
int[] minWeightFromStart = minWeight.clone();
dijkstra(v1);
int[] minWeightFromV1 = minWeight.clone();
dijkstra(v2);
int[] minWeightFromV2 = minWeight.clone();
int result = 0;
// if(minWeightFromStart[N] == Integer.MAX_VALUE && minWeightFromV2[N] == Integer.MAX_VALUE && minWeightFromV1[N] == Integer.MAX_VALUE) {
// result = -1;
// } //-> 100%에서 오답
if(minWeightFromStart[N] == Integer.MAX_VALUE) { //정답처리
result = -1;
} else {
result = Math.min(minWeightFromStart[v1] + minWeightFromV1[v2] + minWeightFromV2[N],
minWeightFromStart[v2] + minWeightFromV2[v1] + minWeightFromV1[N]);
}
System.out.println(result);
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<Node>(Comparator.comparingInt(Node::getWeight));
Arrays.fill(minWeight, Integer.MAX_VALUE);
minWeight[start] = 0;
//starting point
pq.add(new Node(start, 0));
while(!pq.isEmpty()) {
Node cur = pq.poll();
for(Node nxt: adj[cur.id]) {
if(minWeight[nxt.id] > nxt.weight + cur.weight) {
minWeight[nxt.id] = nxt.weight + cur.weight;
pq.add(new Node(nxt.id, minWeight[nxt.id]));
}
}
}
}
}
class Node {
int id;
int weight;
public Node(int id, int weight) {
this.id = id;
this.weight = weight;
}
@Override
public String toString() {
return "Node [id=" + id + ", weight=" + weight + "]";
}
public int getWeight() {
return weight;
}
}
이슈3 : 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력
문제 조건에 맞게 edge case를 마지막에 고려해줘야 한다. 경로가 없을 경우, 시작노드 -> N노드 의 가중치값이 MAX가 될 것이다.
