반응형
BOJ 1854 K번째 최단경로
풀이:
1. 도로가 단방향.
2. 시작점은 경로비용 0 (문제에서 제시)
3. 시작점은 1번도시로 고정
이 전제하에 각 도시에 대해 모든 최단경로를 가장 작은 순으로 정렬했을 때 문제에서 주어지는 K번째 경로비용을 구하면 된다.
다만 모든 최단 경로를 구할 경우 메모리 초과가 발생한다.
따라서 모든 경로를 탐색하면서 각 K번째 최단경로까지만 보관한다.
각 경로의 최단경로를 보관하기 위해 입력받는 순간 정렬되는 Priorityque를 배열로 사용한다.
(PriorityQueue<Integer>[] costList = new PriorityQueue[N]; //도시 개수만큼 생성)
que에 들어가는 순간 정렬되는 효과를 이용한다.
적은 비용은 두고 큰 비용은 그거보다 작은 비용을 만날 경우 빼야하므로 역정렬 사용.
new PriorityQueue<>(Collections.reverseOrder());
반응형
'알고리즘' 카테고리의 다른 글
알고리즘 문제 핀볼 (0) | 2021.06.13 |
---|---|
백준 11437번 LCA (0) | 2021.06.11 |
백준 1238 파티 Java (0) | 2021.05.22 |
백준 1197 최소 스패닝 트리 Java (0) | 2021.05.12 |
백준 1920 수 찾기 (0) | 2021.05.07 |