[BOJ] Q10159 저울

[BOJ] Q10159 저울

Question

Language: Python

Difficulty: Gold 3

해당 문제는 1613 문제와 유사한 방식으로 풀면 된다. 서로 비교를 할 수 없다는 건 서로에게 길이 없다는 것을 뜻하기 때문에 floyd-warshall 알고리즘으로 모든 경로를 다 찾아 준 다음 해당 노드에서 도달할 수 없는 노드의 개수를 찾는다.

Solution

from math import inf
def solution():
    for k in range(1,n_vertex+1):
        for i in range(1, n_vertex+1):
            for j in range(1, n_vertex+1):
                if graph[i][j] > graph[i][k]+graph[k][j]:
                    graph[i][j]=graph[i][k]+graph[k][j]


    for i in range(1,n_vertex+1):
        count=0
        for j in range(1,n_vertex+1):
            if i==j:
                continue
            elif graph[i][j] == inf and graph[j][i] == inf:
                count+=1
        print(count)
        
if __name__ == "__main__":
    n_vertex=int(input())
    n_edge=int(input())
    graph=[[inf]*(n_vertex+1) for _ in range(n_vertex+1)]
    for _ in range(n_edge):
        v1,v2=map(int,input().split())
        graph[v1][v2]=1
    solution()