[백준 10159] 저울 - Python

문제 보기

[사용한 알고리즘]

플로이드-워셜

 

[문제 접근]

물건을 정점, 물건의 무게 비교 결과를 선분으로 표시하여 그래프를 구현합니다. 그래프를 구현하고 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 최단 거리를 계산합니다. 이후 서로 다른 물건이 도달할 수 있으면 비교 결과를 알 수 있고, 도달할 수 없으면 비교 결과를 확인할 수 없다고 생각하였습니다.

 

[알고리즘]

1. 물건의 비교 결과를 이용해서 그래프를 구현합니다.

2. 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 도달 가능 여부를 계산합니다.

3. 도달할 수 없는 물건의 개수를 출력합니다.

 

[코드]

import sys


INF = 1E9


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    maps = [[INF] * n for _ in range(n)]
    for i in range(n):
        maps[i][i] = 0

    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        maps[b - 1][a - 1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])

    result = []
    for i in range(n):
        cnt = 0
        for j in range(n):
            if maps[j][i] == INF and maps[i][j] == INF:
                cnt += 1
        result.append(cnt)

    for i in range(n):
        print(result[i])