플로이드-워셜 대체 왜 이렇게 도는 거야? (헷갈렸던 부분 정리)
·
Data Structures & Algorithms
프로그래머스 문제중 합승 택시 요금 문제를 풀면서 플로이드-워셜을 처음 제대로 파봤는데, 삼중 for문 자체는 외우는 데 5분도 안 걸렸다. 근데 "이게 왜 되는 거지?"를 이해하는 데는 시간이 좀 걸렸다. 특히 dist[i][k] + dist[k][j]처럼 인덱스에 i, k, j가 섞여 나오니까 머릿속에서 잘 안 그려지더라.결국 "그냥 프린트 찍어서 눈으로 보자"로 해결했는데, 그 과정을 정리해본다.일단 코드부터for (int k = 1; k 다익스트라는 "한 정점에서 출발해서 모든 정점까지"의 최단거리를 구하는데, 플로이드-워셜은 "모든 정점 쌍 사이"의 최단거리를 한 번에 구한다. 정점 개수가 적을 때(n≤400 정도) 쓰기 좋다.헷갈렸던 지점: k가 대체 뭐야dist[i][k] + dist[k]..