문제 해결 전략
: 플로이드 워샬
시간복잡도 최적화
- 연산자 비교 시간이 대입하는 시간보다 훨씬 빠르다.
그리고 매번 대입하는 것보다는 연산을 통해서
대입처리하는 것이 상식적으로 좋다.
- 위에거가 연산자 비교했을 때
- 아래거가 min 처리했을 때
-> 12ms차이 나는데, 현재 정점이 100개이고,
플로이드 워셜을 v3승이므로 정점이 1000개라고 한다면,
120ms 차이가 발생한다는 것이다.
주의할점
- 초기화
- i == j 인 경우에는 반드시 0으로 하고, 나머지는 INF 로
- 마지막에 출력할 때는 연결이 안된 경로가 존재할 수 있다.
그에 따른 처리 코드가 반드시 필요하다.
🔥🔥🔥