[python]1956번 운동,변형된 다익스트라

https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1956-%EC%9A%B4%EB%8F%99-%ED%92%80%EC%9D%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[알고리즘] 백준 1956 '운동' 풀이 _ 파이썬

처음 문제를 보고 푸는 방법을 몰라 위 블로그에서 도움을 얻었다.(변형된 다익스트라도 위 블로그에 있습니다)

플로이드 알고리즘으로 싸이클 또한 확인할 수 있다는 것을 알게 되었다.

처음 2차원 배열에 값을 저장할 때 본인 값을 0으로 수정하지 않고 그대로 최댓값으로 설정해놓고

알고리즘을 돌리면 다른 거쳐가는 노드들을 통해 다시 자신한테 돌아오는 경로가 있으면 값이 갱신이 된다.

이것을 통해 싸이클을 판별할 수 있다.

 

import sys
input = sys.stdin.readline
vil,edges = map(int,input().split())
graph = [[1e9 for i in range(vil+1)] for j in range(vil+1)] #비용 값 저장
for i in range(edges):
    fst,scd,thd = map(int,input().split())
    graph[fst][scd] = thd
for k in range(1,vil+1):
    for i in range(1,vil+1):
        for j in range(1,vil+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]) #플로이드 알고리즘
std = 1e9
for i in range(1,vil+1):
    if std>graph[i][i]: #싸이클이 존재할 때
        std = graph[i][i]
print(std if std!= 1e9 else -1)

 

위 블로그에서 플로이드알고리즘 외에도 변형된 다익스트라로 더 효율적으로 풀이된게 있어 나중에는 다양하게 풀이 할 수있게끔 공부 열심히 해야겠다