Baekjoon 1916 최소비용 구하기 JAVA

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201916

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 N 개의 도시가 있고, M 개의 버스가 있을 때 A에서 B까지 갈 수 있는

최소 비용을 출력하는 문제다.

​

다익스트라 알고리즘을 이용해서 문제를 해결했으며,

정렬은 PriorityQueue(우선순위 큐)를 사용하였고 람다식을 이용해 정렬했다

간선 정보는 ArrayList<ArrayList<Edge>>

어레이 리스트 안에 어레이 리스트를 넣는 방식으로 사용했다.

​

처음에 방문, 비용 배열과 어레이 리스트를 다 초기화 시켜 크기를 할당해 주고

이후 입력받은 간선 정보를 어레이 리스트에 넣어준 뒤

주어진 시작점을 pq에 넣어 pq가 빌 때까지 돌면서 최솟값을 찾아 넣어주는 식으로

문제를 해결했다.

cost에 시작 도시 A에서 갈 수 있는 모든 도시에 대한 최솟값이 담겨있기 때문에

cost[B]와 같은 식으로 결과를 출력해 주었다.