플로이드 워셜
![[프로그래머스, Java] 합승 택시 요금](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FOfZu0%2FbtrJlph3AgA%2FVf9wIDAKiAgPXGr3183xQk%2Fimg.gif)
[프로그래머스, Java] 합승 택시 요금
🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72413 😮 문제 해결 방법 최단 거리 알고리즘을 적용하는 것이 문제의 키포인트이다. 모든 도시로부터 출발해 모든 도시로 도착하는 최단 거리를 구해준다. 최단 거리를 구하는 방식은 크게 두가지가 있다. (무방향 양수 그래프 기준) 하나의 정점 기준 최단 거리구하기 → 다익스트라 알고리즘 : 모든 도시에 대해 구해야하므로 for문을 통해 모든 최단 거리를 구한다. 모든 정점 기준 최단 거리 구하기 → 플로이드 워셜 알고리즘 모든 정점에 대한 최단거리를 구하는 알고리즘은 플로이드 워셜을 일반적으로 사용하기 때문에 플로이드 워셜 알고리즘을 통해 문제를 해결한다. (다익스트라 이용시 시간초과 ..