Floyd Warshall
-
[백준 1238] - [플로이드 와샬] - 파티 (JAVA)카테고리 없음 2018. 12. 28. 17:10
문제 링크 : https://www.acmicpc.net/problem/1238이 문제는 다익스트라 알고리즘으로 문제를 풀 수 있지만 플로이드 와샬 알고리즘으로도 풀 수 있다. 1부터 N 까지의 학생의 집을 한번씩 들린다 가정하고 이떄의 값을 K로 둔다. i 부터 j까지 의 거리와 i 에서 K 까지의 거리와 K에서 j 까지의 거리의 합중 최솟값을 최소시간으로 정하면 된다. 플로이드 와샬 알고리즘으로 각 각의 최소 시간을 구한 다음에 각 학생이 파티를 하는 학생에 집에 가고 오는 거리가 제일 큰 학생의 시간을 출력해주면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354..
-
[백준 11404] - [플로이드 와샬] - 플로이드 (JAVA)알고리즘/플로이드 와샬 (Floyd Warshall) 2018. 12. 28. 16:19
문제 링크 : https://www.acmicpc.net/problem/11404이 문제는 새로 접하는 알고리즘인 플로이드 와샬(Floyd Warshall) 알고리즘이다. 최단 경로를 구하는 알고리즘이다. 2차원 배열로 존재하면서 기준점 K를 두고 I에서 J 까지 가는 거리와 I에서 K 까지 갔다가 K에서 J 까지 가는 거리 두가지를 비교하여 최소 값을 최단 거리로 구하면 된다. 문제에서 주어진 예제 입력으로 플로이드 와샬 알고리즘을 공부해보자. 이 문제에서 요구하는 답은 N 개의 도시가 존재하고 1 부터 N까지의 도시각 각각의 도시에 갈 수 있는 최소 비용이다. N x N 의 2차원 배열로 존재하고 각 도시의 도달할 수 있는 최소비용이 저장되면 된다. 비용을 저장하는 배열에는 무한대의 값으로 초기화 해..