[문제 링크]
https://www.acmicpc.net/problem/1446
[난이도]
- Silver 1
[알고리즘]
- DP
- 다익스트라
[코드]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 지름길의 개수
int D = scanner.nextInt(); // 고속도로의 길이
// graph를 생성하고 초기화
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i <= D; i++) {
graph.add(new ArrayList<>()); // 노드의 개수만큼 생성
}
// 지름길 정보를 graph에 추가
for (int i = 0; i < N; i++) {
int u = scanner.nextInt(); // 시작 노드
int v = scanner.nextInt(); // 도착 노드
int w = scanner.nextInt(); // 가중치
if (v <= D) { // 노드범위 이상일경우 추가하지 않는다.
graph.get(u).add(new int[]{v, w}); //
}
}
int[] dist = new int[D + 1]; // 가중치를 기록할 배열
Arrays.fill(dist, Integer.MAX_VALUE); // 초기값은 모두 INF
dist[0] = 0; // 시작 위치는 0
// int[] a 중에서 두번째 요소인 a[1]을 기준으로 큐를 정렬, 즉 가중치(비용)을 기준으로 오름차순 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{0, 0}); // {현재 위치, 현재 비용}
while (!pq.isEmpty()) {
int[] current = pq.poll();
int currentPos = current[0];
int currentCost = current[1];
// 만약 현재 비용이 기록된 비용보다 크다면, 이미 더 적은 비용으로 도달한 경로가 존재하므로 무시
if (currentCost > dist[currentPos]) continue;
// 다음 지점으로 이동 (일반 도로, 현재 위치에서 한 칸 앞으로 이동)
// 현재위치에서 한 칸 앞으로 이동한 위치가 D(도로의 길이, 간선의 범위)를 넘지않는경우
// 현재위치에서 한칸 앞으로 이동한 위치까지의 비용이 기존에 기록된 비용보다 작은 경우
if (currentPos + 1 <= D && currentCost + 1 < dist[currentPos + 1]) {
dist[currentPos + 1] = currentCost + 1; // 다음 위치까지의 비용 갱신
pq.add(new int[]{currentPos + 1, currentCost + 1}); // 우선순위 큐에 추가
}
// 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
for (int[] edge : graph.get(currentPos)) {
int nextPos = edge[0]; // 지름길의 도착 위치
int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
// 지름길을 이용한 비용이 더 적다면 비용 갱신
if (nextCost < dist[nextPos]) {
dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
}
}
}
System.out.println(dist[D]);
}
}[풀이]
일반적인 다익스트라 알고리즘과 같다. 하지만 추가된 부분이 있다.
// 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
for (int[] edge : graph.get(currentPos)) {
int nextPos = edge[0]; // 지름길의 도착 위치
int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
// 지름길을 이용한 비용이 더 적다면 비용 갱신
if (nextCost < dist[nextPos]) {
dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
}
지름길을 이용한 경우의 가중치를 한번 더 생각해주어야 한다는 것이다.
'코딩테스트' 카테고리의 다른 글
| 백준 14502 : 연구소 [JAVA] (0) | 2024.08.09 |
|---|---|
| 백준 1931: 회의실배정 [JAVA] (0) | 2024.07.19 |
| 백준 2156 : 포도주 시식 [JAVA] (0) | 2024.06.27 |
| 백준 2529 : 부등호 [JAVA] (0) | 2024.06.21 |
| 백준 2023 : 신기한 소수 [JAVA] (0) | 2024.06.20 |
