플로이드 워셜

[프로그래머스, Java] 합승 택시 요금

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72413 😮 문제 해결 방법 최단 거리 알고리즘을 적용하는 것이 문제의 키포인트이다. 모든 도시로부터 출발해 모든 도시로 도착하는 최단 거리를 구해준다. 최단 거리를 구하는 방식은 크게 두가지가 있다. (무방향 양수 그래프 기준) 하나의 정점 기준 최단 거리구하기 → 다익스트라 알고리즘 : 모든 도시에 대해 구해야하므로 for문을 통해 모든 최단 거리를 구한다. 모든 정점 기준 최단 거리 구하기 → 플로이드 워셜 알고리즘 모든 정점에 대한 최단거리를 구하는 알고리즘은 플로이드 워셜을 일반적으로 사용하기 때문에 플로이드 워셜 알고리즘을 통해 문제를 해결한다. (다익스트라 이용시 시간초과 ..