https://www.acmicpc.net/problem/5719
문제
최단 경로에 포함되는 도로를 제외하고 구할 수 있는 최단 거리(거의 최단 경로)를 구한다.
흐름
- 최단 거리를 구한다.
- 최단 거리에 포함되는 도로를 없앤다.
- 남은 도로로 다시 최단 거리를 구한다.
구조화
1. 최단 거리를 구하면서 경로를 저장한다.
다익스트라 알고리즘으로 최단 거리를 구하면서 + 그 경로에 포함되는 도로를 따로 저장해야 한다.
🤔 그럼 도로를 언제 저장할건데
일단 다익스트라 알고리즘 구조를 생각했을 때:
while(!pq.isEmpty()) {
큐에서 꺼낸 노드에 방문한다.
현재 노드와 인접한 노드를 차례로 탐색하면서:
더 짧은 거리를 발견하면:
(최적값을 발견했으므로) 새로 계산한 값으로 갱신한다.
그리고 해당 인접 노드를 큐에 추가한다.
}
구조를 보고 생각했을 때 더 짧은 거리를 발견했을 때 블록에서 도로를 저장하면 되겠다는 생각을 할 수 있다.
while(!pq.isEmpty()) {
큐에서 꺼낸 노드에 방문한다.
현재 노드와 인접한 노드를 차례로 탐색하면서:
더 짧은 거리를 발견하면:
(최적값을 발견했으므로) 새로 계산한 값으로 갱신한다.
그리고 해당 인접 노드를 큐에 추가한다.
도로를 저장한다.
}
그런데 문제에서 최단 경로는 여러 개가 있을 수 있다고 언급했으므로, 새로운 최단 거리를 찾았을 때만 경로를 저장하게 되면 다른 최단 경로는 저장할 수가 없다. 그러니까 값이 같을 때도 저장해줘야 하므로 조건문 블록을 추가해준다.
while(!pq.isEmpty()) {
큐에서 꺼낸 노드에 방문한다.
현재 노드와 인접한 노드를 차례로 탐색하면서:
더 짧은 거리를 발견하면:
(최적값을 발견했으므로) 새로 계산한 값으로 갱신한다.
그리고 해당 인접 노드를 큐에 추가한다.
도로를 저장한다.
같은 최단 거리를 발견하면:
도로를 저장한다.
}
여기서 또 드는 의문은
🤔 도로를 어떻게 저장할건데
이 부분에서 고민을 많이 했는데, 최단 경로가 여러 개가 있을 수 있다면 자식 노드와 연결된 부모 노드가 여러 개가 있을 수 있다는 말이다. 여기서 단일 자식 노드와 다수 부모 노드 쌍을 생각했다. 근데 쌍이니까 자연스럽게 Map을 사용해야겠다…는 생각이 들었다.
그래서 `Map<Integer, List<Integer>>` 에 도로를 저장한다.
이 결론에 따라 구조에 다시 변화를 주면:
while(!pq.isEmpty()) {
큐에서 꺼낸 노드에 방문한다.
현재 노드와 인접한 노드를 차례로 탐색하면서:
더 짧은 거리를 발견하면:
(최적값을 발견했으므로) 새로 계산한 값으로 갱신한다.
그리고 해당 인접 노드를 큐에 추가한다.
(새로운 최단 거리이므로) 부모 노드를 갱신한다.
같은 최단 거리를 발견하면:
(같은 최단 거리이지만 다른 경로이므로) 부모 노드를 추가한다.
}
이렇게 하면 최단 경로만 저장할 수 있다!
2. 최단 경로에 포함된 도로 없애기
하지만 여기서 주의해야하는게, 이제 저장된 도로 정보를 로그로 찍어보면 최단 경로 뿐만 아니라 다른 도로도 찍힌다.
🚧 다익스트라는 결국 한 정점에서 모든 정점에 대한 최단 거리를 구하는 알고리즘이라서
모든 정점에 대해 최단 거리를 계산하게 되면 경로를 저장하기 때문에 최단 경로에 포함되는 도로 뿐만아니라 다른 도로도 최단 거리를 계산하면 저장해버린다.
예를 들면 1 → 3 → 6이 최단 경로인데, 1 → 2로 가는 최단 거리를 발견하면 이 도로도 저장한다. 그러니까 이런 경우를 제외하면서 최단 경로에 포함되는 도로만 삭제할 수 있는 방법을 생각해야 한다.
그런데 생각해보면 첫 번째 단계에서 새로운 최단 거리를 찾았을 때 부모 노드를 갱신하게 되므로 도로 정보 맵에 저장된 정보를 따라서 목적지에서 출발지로 따라 올라갈 수 있는 경로는 최단 경로 뿐이다.
그러니까 도착지 → 출발지까지 역으로 올라가면서 지나는 도로를 삭제 처리해준다. 삭제 여부는 `boolean[][]` 배열을 사용해서 삭제했다는 체크만 해준다.
3. 다시 최단 거리 구하기
삭제여부 배열에서 제거 표시된 도로는 건너뛰면서 다익스트라를 수행한다.
구현
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while(true) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); //장소 수
int m = Integer.parseInt(st.nextToken()); //도로 수
//00정지
if(n==0 && m==0) break;
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken()); //시작점
int d = Integer.parseInt(st.nextToken()); //도착점
//맵 생성
Map<Integer, List<Load>> map = new HashMap<>();
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()); //from
int v = Integer.parseInt(st.nextToken()); //to
int p = Integer.parseInt(st.nextToken()); //dist
//방향 가중치 그래프
map.computeIfAbsent(u, k->new ArrayList<>()).add(new Load(v, p));
}
//최단 거리 찾기 + 최단 경로에 포함되는 도로 체크
Map<Integer, List<Integer>> prev = getShortestWays(map, n, s, d);
//최단 경로에 포함되는 도로 삭제하기
boolean[][] removed = new boolean[n][n];
removeShortestWays(removed, prev, d);
//제거된 도로 제외하고 최단 거리 구하기
int res = getAlmostShortestWays(map, removed, n, s, d);
System.out.println(res == Integer.MAX_VALUE ? -1 : res);
}
}
static Map<Integer, List<Integer>> getShortestWays(Map<Integer, List<Load>> map, int n, int s, int d) {
int[] dist = new int[n]; //각 장소까지의 최단 거리
Arrays.fill(dist, Integer.MAX_VALUE); //INF로 초기화
//최단 경로에 포함되는 도로 저장 {자식 노드: [부모노드]}
Map<Integer, List<Integer>> prev = new HashMap<>();
Queue<Load> pq = new PriorityQueue<>(); //min heap
dist[s] = 0; //시작점 초기화
pq.offer(new Load(s, 0));
while(!pq.isEmpty()) {
Load curr = pq.poll();
//연결된 다리 없으면 무시
if(map.get(curr.to) == null) continue;
for(Load next : map.get(curr.to)) {
//이번 다리까지 거리 계산
int newDist = curr.dist + next.dist;
//새로운 거리가 기존 최단 거리보다 짧으면 새로운 최단 경로 발견 -> 업데이트 후 방문
if(newDist < dist[next.to]) {
dist[next.to] = newDist;
pq.offer(new Load(next.to, newDist));
//새로운 최단 경로 발견: 기존 최단 도로 정보 덮어쓰기 (저장되어있던 도로는 이제 최단이 아님)
prev.put(next.to, new ArrayList<>(List.of(curr.to)));
//새로 계산한 거리가 최단 경로와 같을 경우 최단 경로가 여러 개 -> 추가해서 저장
} else if(newDist == dist[next.to]) prev.computeIfAbsent(next.to, k->new ArrayList<>()).add(curr.to);
}
}
return prev;
}
/*
목적지로부터 출발지까지 연결되는 경로는 모두 최단 경로
-아닌 경우 중간에 끊김
*/
static void removeShortestWays(boolean[][] removed, Map<Integer, List<Integer>> prev, int d) {
Deque<Integer> q = new ArrayDeque<>();
q.offer(d); //목적지에서 출발해서 출발지까지 거슬러 올라감
while(!q.isEmpty()) {
int curr = q.poll();
if(prev.get(curr) == null) continue; //인접 노드 없으면 무시
//인접 노드 타고 계속 삭제 처리
for(int next : prev.get(curr)) {
if(removed[next][curr]) continue;
removed[next][curr] = true;
q.offer(next);
}
}
}
static int getAlmostShortestWays(Map<Integer, List<Load>> map, boolean[][] removed, int n, int s, int d) {
int[] dist = new int[n]; //각 장소까지의 최단 거리
Arrays.fill(dist, Integer.MAX_VALUE); //INF로 초기화
Queue<Load> pq = new PriorityQueue<>(); //min heap
dist[s] = 0; //시작점 초기화
pq.offer(new Load(s, 0));
while(!pq.isEmpty()) {
Load curr = pq.poll();
//연결된 다리 없으면 무시
if(map.get(curr.to) == null) continue;
for(Load next : map.get(curr.to)) {
/*
제거된 다리면 무시
*/
if(removed[curr.to][next.to]) continue;
//이번 다리까지 거리 계산
int newDist = curr.dist + next.dist;
//새로운 거리가 기존 최단 거리보다 짧으면 새로운 최단 경로 발견 -> 업데이트 후 방문
if(newDist < dist[next.to]) {
dist[next.to] = newDist;
pq.offer(new Load(next.to, newDist));
}
}
}
return dist[d];
}
static class Load implements Comparable<Load> {
int to, dist;
public Load(int to, int dist) {
this.to=to; this.dist=dist;
}
//짧은 거리 우선
@Override
public int compareTo(Load l) {
return this.dist - l.dist;
}
}
}
'코딩테스트 > 문제풀이' 카테고리의 다른 글
| [백준] 1854. K번째 최단 거리 (0) | 2025.09.13 |
|---|---|
| [백준] 9084. 동전 (1) | 2025.09.11 |
| [백준] 1939. 중량제한 (1) | 2025.08.28 |
| [리트코드] 790. Domino and Tromino Tiling (1) | 2025.08.24 |
| [리트코드] 399. Evaluate Division (7) | 2025.08.14 |