FilesExpand file tree

 main

/

P45_1.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (47 loc) · 2.61 KB

 main

/

P45_1.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (47 loc) · 2.61 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

package ch13;

import java.util.*;

public class P45_1 {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {

// 여행 경로를 출발지 → 도착지 형태의 그래프로 구성

Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();

for (int[] flight : flights) {

// 값이 존재하지 않을 경우 빈 해시맵 생성

graph.putIfAbsent(flight[0], new HashMap<>());

// 출발지에 (도착지, 비용) 추가

graph.get(flight[0]).put(flight[1], flight[2]);

}

// 우선순위 큐 생성, 값은 (도착지, 비용, 진행 경로)로 구성하므로, 정렬은 비용(인덱스 1) 기준

Queue<List<Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.get(1)));

// (도착지, 비용, 진행 경로)를 큐에 삽입, 시작은 출발지 src이며, 비용과 진행 경로는 출발지이므로 당연히 모두 0

pq.add(Arrays.asList(src, 0, 0));

// 큐에 값이 남아 있다면 없어질 때 까지 반복

while (!pq.isEmpty()) {

// 비용이 가장 저렴한 값 추출

List<Integer> cur = pq.poll();

// 우선순위 큐의 항목은 List<Integer>이므로 인덱스 위치로 (도착지, 비용, 진행 경로) 각각 추출

int u = cur.get(0);

int price_u = cur.get(1);

int k_visited = cur.get(2);

// 만약 큐에서 추출한 값이 도착지 dst라면 정답으로 리턴

if (u == dst)

return price_u;

// 진행 경로(k_visited)가 남은 경로(k) 이내에 있다면 처리 계속

if (k_visited <= k) {

// 처리하면서 진행 경로 +1

k_visited += 1;

// u 지점을 출발지로 한 경로가 있다면 처리 시작

if (graph.containsKey(u)) {

// u 지점을 출발지로 한 모든 경로 순회

for (Map.Entry<Integer, Integer> v : graph.get(u).entrySet()) {

// u 지점까지 비용(price_u) + u 지점을 출발지로 한 도착지까지 비용

int alt = price_u + v.getValue();

// 우선순위 큐에 (도착지, 비용, 진행 경로) 삽입

pq.add(Arrays.asList(v.getKey(), alt, k_visited));

}

}

}

}

// 큐에 모든 값이 비워질 때까지 리턴하지 못했다면 경로가 존재하지 않는다는 얘기이므로 -1 리턴

return -1;

}

}