1753번1 [백준 - Java] 1753번 : 최단경로 문제 www.acmicpc.net/problem/1504www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 설명 다익스트라 구현 시 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데, 간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라 시간 복잡도 역시 O(V^2)으로 좋지 못하게 된다. 최단 경로 (다익스트라 알고리즘) FAQ 따라서 인.. 2021. 3. 20. 이전 1 다음 728x90 반응형