백준 101591 [백준]BOJ 10159: 저울 - Python, Floyd-Warshall 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 문제 풀이 노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는 'A가 B보다 무겁다' 혹은 'B가 A보다 무겁다' 두 가지의 경우가 있으므로 방향 그래프가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다... 2024. 4. 7. 이전 1 다음
