컴퓨터공학 💻 도서관📚
최단 경로 알고리즘 문제 1 . 4 본문
주어진 N, M의 범위를 보니 플로이드 워셜 알고리즘은 500개 이상이므로 안 되고
기본 다익스트라 알고리즘도 시간복잡도가 O(N^^2)이므로 시간초과가 나올 수 있기 때문에
우선순위 힙을 이용한 다익스트라 알고리즘으로 구현하면 된다
도시 C에서 출발해서 각각의 노드로 도달하기 위한 최단 거리 값을 구한 뒤에
C에서 도달이 가능한 도시의 개수를 구할 수 있을 것이고
또한, 도시들이 모두 메시지를 받는 데까지 걸리는 시간을 구하기 위해서
도달이 가능한 도시 중에서 가장 큰 비용을 가지는 즉, 가장 거리가 먼 도시에 대한 정보를 출력하면 된다
C++ 코드
자바 코드
'✅🌲강의 복습 노트 > 이코테2021 알고리즘 훈련' 카테고리의 다른 글
서로소 집합 자료구조 . 1 (0) | 2024.11.26 |
---|---|
최단 경로 알고리즘 문제 2 . 5 (0) | 2024.11.24 |
플로이드 워셜 알고리즘 . 3 (0) | 2024.11.23 |
개선된 다익스트라 알고리즘 . 2 (0) | 2024.11.22 |
다익스트라 최단 경로 알고리즘 개념 . 1 (0) | 2024.11.20 |
Comments