[Python][백준 1956] 운동

https://www.acmicpc.net/problem/1956

1956번: 운동

---

/*
신경써야 할 부분은 바로 :
1. 일방통행 (양방통행 X)
2. 거리의 합이 가장 작은 사이클을 찾아야 하며, 없으면 -1 출력
3. 플로이드 워셜을 통해 최단 거리를 계산할때 사이클이 있어야 하므로 스스로를 0으로 초기화 하지 않음
4. 나온 결과물 중 INF가 아닌 가장 작은 값을 출력

사이클 만드는 접근법만 생각해내면 간단한 응용이었다.
*/

---

import sys
input = sys.stdin.readline
 
INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    # 최단 경로 행렬 초기화
    # 0 if i == j else
    dist = [[ graph[i][j] if graph[i][j] != 0 else INF for j in range(n)] for i in range(n)]
 
    # 동적 프로그래밍을 통한 갱신
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist


v,e = map(int, input().split())
graph = [[INF for _ in range(v+1)] for _ in range(v+1)]

for i in range(e) :
    a,b,c = map(int, input().split())
    
    graph[a][a] = 0
    graph[b][b] = 0
    graph[a][b] = c

shortest_paths = floyd_warshall(graph)

path = []

for row in shortest_paths[1:]:
    path.append(row[1:])
    
result = INF

for i in range(v) :
    # print(path[i][i])
    if path[i][i] == INF :
        continue
    result = min(result,path[i][i])

if result == INF : 
    print(-1)
else :
    print(result)

---

풀 때 어려웠던 점 또는 느낀점 :

그리 어렵진 않았고 플로이드 워셜로 풀 수 있는 문제 유형을 파악하기 위해

계속해서 플로이드 워셜 문제를 풀고 있다.

좀 더 어려운 문제를 성공하고 나면 다른 문제를 풀어야겠다.

---

참고할만한 다른 사람 코드 :

import heapq as hq

V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
#거리를 저장할 배열을 2차원으로
dist = [[1e9] * (V+1) for _ in range(V+1)]

heap = []
for _ in range(E):
    x, y, c = map(int, input().split())
    graph[x].append([c, y])
    dist[x][y] = c
    #heap에도 비용, 출발지, 도착지 3개의 값을 넣어준다.
    #유효한 경로 값을 다 넣어줌
    hq.heappush(heap, [c, x, y])


while heap:
    #최소 비용의 경로를 먼저 뽑아주고 (d:비용, s:출발, g:도착)
    d, s, g = hq.heappop(heap)
    #출발지와 도착지가 같다면 사이클!
    #heap을 이용하기 때문에 처음 나온 사이클이 가장 비용이 작은 사이클이므로 break 해버려도 됨! -> 여기서 시간이 굉장히 절약되는 듯 
    if s == g:
        print(d)
        break
    #d 값이 이미 저장된 비용보다 크다면 넘겨버림
    if dist[s][g] < d:
        continue
        
    #g에서 갈 수 있는 노드들을 검사
    for nd, ng in graph[g]:
    	# s->g->ng로 가는 비용
        new_d = d + nd
        # s->g->ng로 가는게 s->ng보다 빠르다면 값 갱신해주고 heap에 넣어줌
        if new_d < dist[s][ng]:
            dist[s][ng] = new_d
            hq.heappush(heap, [new_d, s, ng])
else:
    #heap 다 돌았는데 없다면 -1
    print(-1)
    
# 출처 : 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

다익스트라를 활용한 풀이이다.

플로이드 워셜을 숙달하고 나면 다익스트라를 하는것도 좋아보인다.