[BOJ] Q2458 키순서

[BOJ] Q2458 키순서

Question

Language: Python

Difficulty: Gold 4

해당 문제는 10159와 유사한 방식으로 풀이하면 되는 문제이다.

floyd_warshall algorithm을 활용해서 임의의 노드에 대해서 다른 노드에 대한 거리(도달 여부)를 구해서 해당 노드에 대한 순서를 구할 수 있다.

해당 문제에서의 간선은 노드 간에 비교가 가능하다는 것을 의미하기 때문에 노드 간에 경로가 있다는 것은 노드들간에 비교가 가능함을 의미한다.

floyd-warshall

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

Solution

from math import inf
def solution():
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])
   
    answer=0
    for i in range(n):
        graph[i][i]=0
        count=0
        for j in range(n):
            if graph[i][j] != inf or graph[j][i] != inf:
                count+=1
        
        if count==n:
            answer+=1
    
    print(answer)
            
if __name__ == "__main__":
    n,m=map(int,input().split())
    graph=[[inf] * n for _ in range(n)]

    for _ in range(m):
        v1,v2=map(int,input().split())
        graph[v1-1][v2-1]=1
    
    solution()