[백준 2024/02/26] 1956번 운동

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

1956번: 운동

 

1. 접근 방법

Floyd - Warshall 로 이 문제를 접근하였다.

각각의 노드에 대해서, a 에서 b로 가는 최솟값이 나타날 수 있다는 점에서 floyd - warshall 이 장점이 있는 것 같다.

처음에 Dijkstra로 문제를 풀었으나, 해당 문제에서는 시간 초과가 나서 풀 수 없었다.

 

일반적인 floyd - warshall 코드에, 

for a in range(1, n + 1, 1):
    for b in range(1, n + 1, 1):
        if dist[a][b] != 0 and dist[a][b] != INF and dist[b][a] != INF:
            total.append(dist[a][b] + dist[b][a])

 

이 부분만 추가하였다. 저장된 값중, 0 이거나, INF 가 아닌 것을 대상으로 진행하였다.

0 인 경우는 1번 노드에서 1번 노드로 진행하는 경우가 해당될 것이기 때문에 pass 해주었으며, 

INF 경우엔 도착할 수 있는 방법이 없었기 때문에 INF가 저장되어 있는 것이기 때문에 pass 해주었다.

 

cycle을 만들어야 하기 때문에, floyd- warshall로 완성된, dist[a][b] 에다가 즉, a: 시작 노드, b: 도착 노드 에다가 다시, 

dist[b][a]를 더해주면 된다 ( 도착 노드에서 시작 노드로). b에서 다시 a로 돌아간다면 최솟값으로 저장된 dist에 다시 되돌아가는 cycle을 만들어 주는 것이기 때문에, 최소 사이클 도로 길이의 합을 찾는데 딱이다.

 

이후 최소 cycle들을 저장한 total에서 min 값을 출력해주었다. 비어있다면, cycle이 없는 것이기 때문에 -1을 출력해주었다.

2. 코드

INF = int(1e9)


def floyd_warshall(n, e):
    dist = [[INF] * (n + 1) for _ in range(n + 1)]

    for idx in range(1, n + 1):
        dist[idx][idx] = 0

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

    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    total = []
    for a in range(1, n + 1, 1):
        for b in range(1, n + 1, 1):
            if dist[a][b] != 0 and dist[a][b] != INF and dist[b][a] != INF:
                total.append(dist[a][b] + dist[b][a])
    return total


n, e = map(int, input().split())

total = floyd_warshall(n, e)

if total != []:
    print(min(total))
else:
    print(-1)