저울
-
[Python] 백준 10159 저울알고리즘/문제풀이 2021. 7. 31. 18:31
1. 문제 링크 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 문제 요약 비교 결과를 알 수 없는 물건의 개수 구하기 3. 아이디어 정리 플로이드와샬을 이용해 모든 노드에서 다른 노드 경로 구하기 a > b 가는 경로가 없는 경우(비교 결과를 알 수 없는 경우), count + 1 해주기 플로이드와샬 개념 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 2차원..