플로이드와샬2 [알고리즘] 파티 (백준 1238번) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 최단 시간만에 X번까지 왕복하는 시간을 구해야한다. 즉 각 마을에서 X번까지의 최단 시간, X번에서 각 마을까지의 최단 시간을 둘 다 구해야한다. 가장 쉽게 생각할 수 있는 방법은 플로이드 와샬로 모든 구간의 최단 시간을 구하는 것이다. 시간이 오래 걸리지만 풀긴 풀 수 있는 것 같다. (사실 1000의 3제곱이면 10억인데 못 풀 거라 생각했는데 풀긴 풀더라...) 하지만 X번까지의 왕복 정보 외에는 다른 정보들은 필요가 없다... 2020. 10. 7. [알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘 플로이드 와샬 (Floyd-Warshall) 유향 그래프에서 '모든 정점' → '모든 정점' 까지의 최단 경로를 구하는 알고리즘이다. 시간복잡도 : O(N ^ 3) , (N은 노드의 수) 삼중 반복문을 사용하기에 N의 크기가 상대적으로 적을 때 사용해야한다. 알고리즘 정점 i → 정점 j 까지의 최단 거리를 저장하는 dist[][] 배열을 둔다. dist 초기화 i == j : 0 i → j 까지의 간선이 존재한다면 dist[i][j] = w[i][j] i → j 까지의 간선이 존재한다면 dist[i][j] = INF (무한대) 삼중 반복문 실행 첫번째 반복문 k = 1 ~ N : 거쳐가는 정점 두번째 반복문 i = 1 ~ N : 시작점 세번째 반복문 j = 1 ~ N : 도착점 dist[i][j] = .. 2020. 10. 3. 이전 1 다음
