티스토리 뷰
풀이
방향성이 있으므로 다익스트라 알고리즘을 이용하여 해결하는 문제다.
이 문제를 처음에는 인접행렬로 다가갔다. 결과는 메모리 초과가 나왔다. 아무래도 정점과 간선의 수가(1≤V≤20,000, 1≤E≤300,00) 많으니 인접행렬로는 무리가 있다고 생각한다.
결국 인접 리스트를 이용하여 문제를 해결하였다.
인접 행렬과의 차이점은 인접행렬은 비용을 최소화 하기위해 모든 정점을 확인하지만 인접 리스트는 인접한 정점들만 확인하면 된다.
코드
'알고리즘' 카테고리의 다른 글
| <baekjoon> 구슬 찾기 (0) | 2020.09.07 |
|---|---|
| <baekjoon> 미세먼지 안녕 (0) | 2020.09.05 |
| <SWEA> 하나로 (0) | 2020.09.03 |
| <baekjoon> 점프 점프 (0) | 2020.08.31 |
| <baekjoon> 회전하는 큐 (0) | 2020.08.30 |