반응형
https://www.acmicpc.net/problem/5719
[ 문제풀이 ]
한 정점에서 다른 한 정점으로 가는 최단 경로를 구하는 것이기 때문에 다익스트라 알고리즘을 사용하면 된다.
초기에는 다익스트라로 최단 경로를 구한 후 최단경로가 갱신될 때까지 간선 제거+다익스트라를 반복하였다. 하지만 최단 경로가 2개 이상인 경우 문제가 발생하였다.
위와 같은 경우 하나의 최단 경로 간선을 제거한다면 두 번째 다익스트라에서 1->4->3의 경로가 존재하게 된다. 하지만 실제로는 1->2, 2->3, 2->4, 4->3, 4개의 간선이 제거되기 때문에 두 번째 다익스트라에서 최단 경로는 존재하지 않는다.
따라서 다익스트라를 반복하지 말고 최단 경로를 리스트로 저장하여 한번에 경로를 제거해준다.
다른 풀이를 살펴보니 경로를 저장해주지 않고도 dp로 역경로를 추적할 수 있다는 것을 알게 되었다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static class Edge implements Comparable<Edge> {
int to, cost;
public Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
static final int INF = (int) 1e9;
static int N, M, S, D;
static int[] dist;
static List<Integer>[] path;
static List<Edge>[] edgeList;
static PriorityQueue<Edge> pq;
static boolean[][] check;
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));)
{
edgeList = new ArrayList[501];
path = new ArrayList[501];
dist = new int[501];
check = new boolean[501][501];
pq = new PriorityQueue<>();
for (int i = 0; i < 501; ++i) {
edgeList[i] = new ArrayList<>();
path[i] = new ArrayList<>();
}
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 0 && M == 0) break;
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; ++i) {
st = new StringTokenizer(br.readLine());
int U = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
edgeList[U].add(new Edge(V, P));
}
dijkstra();
removeEdge(D);
dijkstra();
bw.write((dist[D] == INF ? -1 : dist[D]) + "\n");
for (int i = 0; i < N; ++i) {
edgeList[i].clear();
path[i].clear();
Arrays.fill(check[i], false);
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static void dijkstra() {
for (int i = 0; i < N; ++i) {
dist[i] = INF;
}
dist[S] = 0;
pq.offer(new Edge(S, 0));
while (!pq.isEmpty()) {
Edge e = pq.poll();
if (dist[e.to] < e.cost) continue;
for (Edge ne : edgeList[e.to]) {
if (check[e.to][ne.to]) continue;//제거된 간선
//같은 최단 경로라면 path에 저장
if (dist[ne.to] == e.cost + ne.cost) {
path[ne.to].add(e.to);
}
//새로운 최단 경로라면 기존의 path를 제거 후 저장
else if (dist[ne.to] > e.cost + ne.cost) {
dist[ne.to] = e.cost + ne.cost;
path[ne.to].clear();
path[ne.to].add(e.to);
pq.offer(new Edge(ne.to, dist[ne.to]));
}
}
}
}
public static void removeEdge(int v) {
for (int bv : path[v]) {
if (check[bv][v]) continue;
check[bv][v] = true;
removeEdge(bv);
}
}
}
반응형
'Problem Solving > 백준' 카테고리의 다른 글
백준 2211 : 네트워크 복구 (0) | 2021.07.05 |
---|---|
백준 1525 : 퍼즐 (0) | 2021.07.04 |
백준 16437 : 양 구출 작전 (0) | 2021.07.03 |
백준 2239 : 스도쿠 (0) | 2021.07.01 |
백준 1593 : 문자 해독 (0) | 2021.06.29 |
댓글