코딩스토리

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 작년 8월에 처음 공부한 뒤 지금까지 한 번도 복습하지 않았다.. 당연히 그때도 어려웠지만 지금은 완전히 까먹은 상태여서 언젠간 해야지 하다가 결국 어제오늘 복습을 했다. 사실 bfs 문제를 풀다가 '가중치'가 일정하지 않은 문제를 만나서 급하게 다익스트라를 공부한거긴 함ㅎㅎ 어쨌든 문제를 분석해보면 도로들은 단방향으로 이루어져있고 -> 단방향 그래프 각각의 ..

백준 1753번 - 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 최단경로 문제는 시간 복잡도가 1초이고 정점의 개수가 20000개, 간선의 개수가 300000개 이므로 단순한 그래프 문제 푸는 방식으로 풀게 되면 시간 초과가 나게 된다. 참고로 다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV)이다. 다익스트라 알고리즘을 간단히 복습해 보자. 먼저 다익스트라 알고리즘의 특징은 간선의 가중치가 모두 ..