길 찾기 알고리즘은 Dijkstra밖에 몰랐기에, 당당하게 dijkstra로 풀었지만, 효율성 검사에서 2개가 틀리는 바람에 새로운 알고리즘을 알게 됐다.
새롭다고 해야할까... 플로이드-워셜 알고리즘을 공부하고 나니 이렇게 간단한 접근방법이 있었다니... 정신이 멍해졌다.
Dijkstra로 풀었던 코드
import java.util.*;
class Solution {
static class Graph{
int V;
List<List<Node>> adj = new ArrayList<>();
public Graph(int V){
this.V = V;
for(int i=0; i<=V; i++){
adj.add(new ArrayList<>());
}
}
public void addEdge(int start, int end, int weight){
adj.get(start).add(new Node(end, weight));
adj.get(end).add(new Node(start, weight)); // 양방향 그래프이므로 역방향도 추가
}
public int[] dijkstra(int startVertex){
int[] dist = new int[V+1];
PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->a.weight - b.weight);
Arrays.fill(dist, Integer.MAX_VALUE);
dist[startVertex] = 0;
pq.add(new Node(startVertex, 0));
while(!pq.isEmpty()){
int currentVertex = pq.poll().vertex;
List<Node> lst = adj.get(currentVertex);
for(Node node : lst){
int vertex = node.vertex;
int weight = node.weight;
int currentAdjDist = dist[currentVertex] + weight;
if(currentAdjDist < dist[vertex]){
dist[vertex] = currentAdjDist;
pq.add(new Node(vertex, currentAdjDist));
}
}
}
return dist;
}
}
static class Node{
int vertex;
int weight;
public Node(int vertex, int weight){
this.vertex = vertex;
this.weight = weight;
}
}
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = Integer.MAX_VALUE;
Graph graph = new Graph(n);
for(int[] fare : fares){
graph.addEdge(fare[0], fare[1], fare[2]);
}
int[] allDist = graph.dijkstra(s);
for(int i=1; i<=n; i++){
int AB = allDist[i];
int A = allDist[a];
int B = allDist[b];
answer = Math.min(AB + A + B, answer);
}
return answer;
}
}
어느 지점까지 합승하는게 유리한지 그리디한 방법으로 알 수가 없어, 그냥 모든 경우의 수를 다 구해놓은 뒤 최솟값을 구하기로 했다.
합승하는 위치 AB에서 A와 B를 다시 dijkstra를 돌려 구해야 했는데, AB의 위치는 모든 노드를 체크해야하므로, 시간 복잡도를 O(V * (V+E) logV)로 계산했다.
간선의 최대 개수는 V^2이므로 O(V^3logV)라고 예상했는데 노드개수가 200개니까 문제없을거라고 생각했다.
하지만 예상보다 훨씬 시간이 오래 걸렸고, 다른 알고리즘을 물어보니 플로이드워샬 알고리즘이라는 것이 있다고...
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
int INF = Integer.MAX_VALUE;
int[][] dist = new int[n+1][n+1];
// 초기화
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
// fares 정보로 초기화
for(int[] fare : fares) {
int c = fare[0];
int d = fare[1];
int f = fare[2];
dist[c][d] = f;
dist[d][c] = f; // 양방향
}
// 플로이드-와샬 알고리즘
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
int answer = INF;
for(int k = 1; k <= n; k++) {
int temp = dist[s][k] + dist[k][a] + dist[k][b];
if(temp < answer) answer = temp;
}
return answer;
}
}dijkstra와 매우 비슷한 알고리즘인 듯 한데, startVertex에서 vertex까지의 distance를 구하기 위해선 dijkstra가 좋지만
모든 노드 쌍의 최단거리를 구해야 할 때는 플로이드워샬이 더 낫다고 한다.
각 노드마다 dijkstra를 돌려야하니까 오히려 시간이 펑...
좋은걸 배웠다