문제
문제 설명
며칠전에 풀었던 플로이드 문제와 같은 정점부터 정점까지의 최소 경로를 구하는 문제이다.
플로이드 문제와 다른 점은 이번 문제에서는 출발점에서 도착점까지의 최소경로만 구하면 되는 것이다.
첫번째 시도
나는 처음에 아래와 같이 플로이드-워셜 알고리즘을 사용해서 풀었는데 예제 입력은 맞았지만 제출해보니 틀렸다고 나왔다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_1916 {
static int n;
static int m;
static int startCity, endCity;
static int[][] cost;
static int INF = 100000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
cost = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i == j) {
cost[i][j] = 0;
} else {
cost[i][j] = INF;
}
}
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int dest = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
cost[start][dest] = weight;
}
StringTokenizer st = new StringTokenizer(br.readLine());
startCity = Integer.parseInt(st.nextToken());
endCity = Integer.parseInt(st.nextToken());
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <=n; j++) {
cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
}
}
}
System.out.println("Cost");
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
System.out.print(cost[i][j] + "\t");
}
System.out.println();
}
System.out.println(cost[startCity][endCity]);
}
}
그래서 다른 블로그를 찾아보니 플로이드-워셜은 모든 정점 -> 모든 정점의 최단 거리를 구할 때는 효과적이지만 한 정점에서 출발하는 문제를 풀때는 좋지 않다는 것을 알았다.
따라서 이번 문제에서는 다익스트라 알고리즘을 사용해야 한다.
🔎 다익스트라 알고리즘이란?
다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점에서부터 다른 정점들까지의 최단 거리를 계산한다.
다익스트라 알고리즘을 구현할때는 우선순위 큐 또는 인접행렬을 이용하는데 이번 문제에서는 우선순위 큐를 사용하겠다.
우선순위 큐의 시간 복잡도는 O(mlog n) 이고 인접 행렬로 표현된 그래프의 경우 시간 복잡도는 O(n^2) 이기 때문이다.
다익스트라 알고리즘 구현 방법
Node클래스 만들기
static class Edge implements Comparable<Edge> {
int dest, weight;
public Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}위 코드와 같이 해당 정점에서 어떤 정점으로 가는지 저장하는 변수 dest 와 비용을 저장하는 변수 weight 를 사용하고우선순위 큐 로 구현하기 때문에 비교를 위한 compareTo 메소드를 Override 해준다.
- 사용할 배열 만들기
입력들을 저장할 graph 와 최종적으로 비용이 저장될 배열 dist 를 만든다.
여기서 dist 배열은 처음에 INF 값으로 초기화한다.
이번 문제에서 INF는 문제 조건에 맞게 1,000 * 100,000 인 100,000,000으로 초기화했다.
graph = new ArrayList[n + 1];
dist = new int[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
dist[i] = INF;
}- 우선순위 큐 구현
일단 처음에는 시작점을 우선순위 pq에 넣어준 후 시작점의 dist를 0으로 초기화 한후 아래와 같은 과정을 반복한다.
- 큐에서 최소 비용의 노드를 선택한다.
우선순위 큐에서poll()을 호출해서 가장 작은 비용의 노드를 선택한다.
Edge cur = pq.poll();
int curNode = cur.dest;
int curWeight = cur.weight;- 인접 노드 탐색
선택한 노드의 인접 노드들을 탐색하여 최소 비용을 갱신한다.
갱신된 노드는 다시 우선순위 큐에 추가한다.
for (Edge edge : graph[curNode]) {
int nextNode = edge.dest;
int nextWeight = curWeight + edge.weight;
if (dist[nextNode] > nextWeight) {
dist[nextNode] = nextWeight;
pq.add(new Edge(nextNode, nextWeight));
}
}이와 같은 방식으로 다익스트라를 구현할 수 있고 이 다익스트라를 사용해서 푼 이번 문제의 전체 코드는 아래와 같다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main_1916 {
static int n, m, startCity, endCity;
static ArrayList<Edge>[] graph;
static int[] dist;
static int INF = 100000000;
static class Edge implements Comparable<Edge> {
int dest, weight;
public Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
dist = new int[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
dist[i] = INF;
}
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int dest = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
graph[start].add(new Edge(dest, weight));
}
StringTokenizer st = new StringTokenizer(br.readLine());
startCity = Integer.parseInt(st.nextToken());
endCity = Integer.parseInt(st.nextToken());
dijkstra(startCity);
System.out.println(dist[endCity]);
}
public static void dijkstra(int start) {
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Edge cur = pq.poll();
int curNode = cur.dest;
int curWeight = cur.weight;
if (dist[curNode] < curWeight) {
continue;
}
for (Edge edge : graph[curNode]) {
int nextNode = edge.dest;
int nextWeight = curWeight + edge.weight;
if (dist[nextNode] > nextWeight) {
dist[nextNode] = nextWeight;
pq.add(new Edge(nextNode, nextWeight));
}
}
}
}
}
정리
다익스트라 알고리즘 과 플로이드-워셜 알고리즘 의 차이점에 대해서 알았고 문제를 풀 때 어떤 알고리즘을 선택을 해야하는지에 대해서 알았다.
개미는 오늘도 일을 합니다.