https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용해서 풀어주었다. 블로그 글 참고. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 sunghyun98.tistory...

최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 구하는 다익스트라 알고리즘과 플로이드 워셜은 다르다. 다익스트라 알고리즘은 1차원 리스트를 이용하지만 플로이드 워셜 알고리즘은 2차원 리스트를 사용한다. 또한 다익스트라는 방문하지않은 노드 중에서 최단경로를 찾지만 플로이드 워셜은 방문하지않았는지 했는지 관심이 없다. 플로이드 워셜의 점화식 노드의 개수가 N일 때 N번 만큼 2차원 리스트를 갱신하다. 1~N번까지의 노드를 한번씩 K로 정해준 뒤 K를 제외한 N-1개의 노드 중에서 서로 다른 노드 A, B를 고른다. K를 거쳐가는 A-K 경로와 K-B 경로의 가중치를 더해서 기..