[백준]BOJ 10159: 저울 - Python, Floyd-Warshall

10159번: 저울 (acmicpc.net)

10159번: 저울

문제

풀이

노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는  'A가 B보다 무겁다' 혹은 'B가 A보다 무겁다' 두 가지의 경우가 있으므로 방향 그래프가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다. (아래의 코드에서 엣지의 방향은 무거운 쪽에서 가벼운 쪽으로 했으며. 반대로 해도 상관 없다.)

 

문제에서 각 물건에 따라서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하라고 했기 때문에, 노드에서 다른 노드로 가는 모든 경우의 수를 알아야 한다. 따라서 다익스트라 알고리즘을 n번 쓰거나 플로이드-워셜 알고리즘을 한 번만 쓰면 된다.

코드

n = int(input())
m = int(input())
inf = 987_654_321
graph = [[inf] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1

for mid in range(1, n + 1):
    for start in range(1, n + 1):
        for end in range(1, n + 1):
            if graph[start][end] > graph[start][mid] + graph[mid][end]:
                graph[start][end] = graph[start][mid] + graph[mid][end]

for i in range(1, n + 1):
    count = 0
    for j in range(1, n + 1):
        if graph[i][j] == inf and graph[j][i] == inf:
            count += 1
    print(count - 1)