Floyd-Warshall

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 풀이 문제를 간단히 하는 것이 중요하다. 이 문제에서 원하는 것은 S에서 시작해서 A와 B 노드로 가야하는데, 그 최단 거리를 요구하고 있다. 그러면 둘이 헤어지는 지점이 존재할 것이고, 이 헤어지는 지점은 S일 수도 있다(문제에서 주어진 내용이다). 그러면 헤어지는 지점을 M이라고 했을때, 우리가 구해야 하는 것은 S → M, M → A, M → B의 최단거리들의 합이다. 문제가 최단거리를 구하는 문제로 단순화 되었다. 음수 사이클이 존재하지 않으므로, 다익스트라 알고리즘이나 플로이드 워셜 알고리즘을 사용하면 된다. 만약 다익스트라를 사용한다면 M을 우리가 모르므로 모든 노드에 대해서 다익스트라 알고리즘을 적용해보고 M을 찾아야 한다. 플로이드 워셜은 모든 노드 상호간의 최단거리를 알 수 있고, 노드의 개수도 200개가 상한이기 때문에 플로이드 워셜을 쓰는 것이 훨씬 간단하게 풀 수 있다. ...

문제 https://www.acmicpc.net/problem/10159 풀이 노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는 ‘A가 B보다 무겁다’ 혹은 ‘B가 A보다 무겁다’ 두 가지의 경우가 있으므로 방향 그래프 가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다. (아래의 코드에서 엣지의 방향은 무거운 쪽에서 가벼운 쪽으로 했으며. 반대로 해도 상관 없다.) 문제에서 각 물건에 따라서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하라고 했기 때문에, 노드에서 다른 노드로 가는 모든 경우의 수를 알아야 한다. 따라서 다익스트라 알고리즘을 n번 쓰거나 플로이드-워셜 알고리즘을 한 번만 쓰면 된다. ...