Q. 1981 자바 : k번째 최단경로 찾기
Q. 1981 자바 : k번째 최단경로 찾기
문제 : boj.kr/1854
P4 난이도의 문제이다.
문제를 간단히 설명하자면
1 ~ n번도시에 대한 그래프가 주어졌을 때 1번 도시에서부터 2, 3, .. n번 도시까지의 k번째 최단경로의 소요시간을 구하는 문제이다.
처음 문제를 보고 떠올린 아이디어는 거의 최단 경로에서 사용했던 아이디어이다.
2번째 최단경로를 구하는 문제이며
최단 경로 알고리즘을 사용해 최단 경로를 구하고
역방향 그래프와 최단 경로 결과값을 활용해서 지나온 경로를 추적하며 방문한 도로들을 삭제한 뒤
다시 최단 경로 알고리즘을 사용해 2번째 최단 경로를 구하는 문제였다.
하지만 k가 최대 100이므로 위 과정을 최대 100번 반복하는건 시간 초과가 우려됬기에
다른 방법을 찾아야 했고, 아이디어는 아래와 같았다.
1번 도시에서 n번 도시까지 도착하는 경우의 수는 여러개이지만, 다익스트라 알고리즘은 최소값만을 활용한다.
그렇다면, 최소값이 아닌 1번 도시부터 n번 도시까지 도착하는 경우의 수를 k개 저장한다면 k번째 최단경로의 소요시간을 알 수 있다.
따라서 아래와 같은 방법으로 풀었다.
최단경로를 저장할 때 우선순위 큐를 사용하는 방법과, List를 사용하는 방법이 있었기에 두 방법으로 풀어봤다.
1. 최단경로 저장에 우선순위 큐를 사용하는 방법
1. 그래프 입력을 받는다.
2. 다익스트라 알고리즘을 활용해 최단 경로를 구한다.
2-1. 최단경로 k개를 저장해야하므로, 최단경로 저장에 우선순위 큐(내림차순)를 사용한다.
2-2. 1번 도시에서 n번 도시까지 저장된 최단경로가 k개 미만인경우 최단경로를 저장한다.
2-3. 1번 도시에서 n번 도시까지의 저장된 최단경로가 k개 이상일 경우 저장된 최단경로의 최대값과 비교해 갱신한다.
코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static StringTokenizer st;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static class Edge {
int idx, cost;
Edge(int idx, int cost) {
this.idx = idx; this.cost = cost;
}
}
static int n, m, k;
static ArrayList<Edge>[] graph;
static PriorityQueue<Integer>[] dist;
static int MAX_VALUE = Integer.MAX_VALUE / 2 - 1;
static void input() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
graph = new ArrayList[n + 1];
dist = new PriorityQueue[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
dist[i] = new PriorityQueue<>((o1, o2) -> o2 - o1);
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[start].add(new Edge(end, cost));
}
}
static void pro() {
dijkstra(1);
for (int i = 1; i <= n; i++) {
if (dist[i].size() < k) System.out.println(-1);
else System.out.println(dist[i].poll());
}
}
static void dijkstra(int start) {
PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
dist[start].add(0);
pq.add(new Edge(start, 0));
while (pq.size() != 0) {
Edge cur = pq.poll();
for (Edge next: graph[cur.idx]) {
int nextCost = cur.cost + next.cost;
if (dist[next.idx].size() < k) {
dist[next.idx].add(nextCost);
pq.add(new Edge(next.idx, nextCost));
continue;
}
if (dist[next.idx].peek() <= nextCost) continue;
nextCost = Math.min(dist[next.idx].poll(), nextCost);
dist[next.idx].add(nextCost);
pq.add(new Edge(next.idx, nextCost));
}
}
}
public static void main(String[] args) throws IOException {
input();
pro();
}
}2. 최단경로 저장에 List를 사용하는 방법
1. 그래프 입력을 받는다.
2. 다익스트라 알고리즘을 활용해 최단 경로를 구한다.
2-1. 최단경로 k개를 저장해야하므로, 최단경로를 저장에 List를 사용한다.
2-2. 저장된 최단경로가 k개를 초과한다면 저장하지 않고 넘어간다.
2-3. 일반적인 다익스트라 알고리즘과 다르게, 우선순위큐에서 값을 꺼내면서 최단경로값을 저장한다. 2-2번 로직이 있기에 가능하다.
2-4. 일반적인 다익스트라 알고리즘과 다르게, 방문하는 모든 정점에 대한 정보를 우선순위큐에 저장한다. 그렇기에 2-3번 로직이 반드시 필요하다.
코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static StringTokenizer st;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static class Edge {
int idx, cost;
Edge(int idx, int cost) {
this.idx = idx; this.cost = cost;
}
}
static int n, m, k;
static ArrayList<Edge>[] graph;
static ArrayList<Integer>[] dist;
static int MAX_VALUE = Integer.MAX_VALUE / 2 - 1;
static void input() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
graph = new ArrayList[n + 1];
dist = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
dist[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[start].add(new Edge(end, cost));
}
}
static void pro() {
dijkstra(1);
for (int i = 1; i <= n; i++) {
if (dist[i].size() < k) System.out.println(-1);
else System.out.println(dist[i].get(k - 1));
}
}
static void dijkstra(int start) {
PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
pq.add(new Edge(start, 0));
while (pq.size() != 0) {
Edge cur = pq.poll();
if (dist[cur.idx].size() > k) continue;
dist[cur.idx].add(cur.cost);
for (Edge next: graph[cur.idx]) {
if (dist[next.idx].size() > k) continue;
int nextCost = cur.cost + next.cost;
pq.add(new Edge(next.idx, nextCost));
}
}
}
public static void main(String[] args) throws IOException {
input();
pro();
}
}