[백준] 1956. 운동

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

---

접근 방법: 플로이드-워셜 알고리즘

• 주어진 그래프의 모든 노드에서 자기자신으로 이어지는 경로 중 최단 경로를 찾는 문제이므로 플로이드-워셜 알고리즘으로 풀 수 있다.
• 보통의 경우 자기 자신으로 돌아오는 루트를 계산에서 제외하기 위해 초기값을 0으로 잡고 시작하지만, 이를 0으로 잡지 않고 무한대로 준다면 자기 자신으로 돌아오는 경로에 대해서도 추적이 가능하다.
• 테스트케이스의 최대 노드 갯수도 400개 정도로 적게 잡혀있으므로 충분히 시간 안에 돌릴 수 있을 것이다.

코드

# https://www.acmicpc.net/problem/1956
import sys
from collections import defaultdict


INF = int(1e9)
input = sys.stdin.readline
V, E = map(int, input().split())
graph = defaultdict(list)
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))


# 문제의 조건에서 노드의 갯수가 (2 <= V <= 400)이므로 플로이드-워셜 알고리즘을 사용해 볼 수 있다.
# CPython으로 제출시 타임오버, PyPy로 제출시 아슬아슬하게 오버되지 않은 것을 확인했다.
# 런타임(PyPy) 1304ms
def floyd_warshall(graph, V):
    dist = [[INF] * (V + 1) for _ in range(V + 1)]

    # # 사이클을 찾아야 하므로 자기 자신으로 돌아오는 경로를 0으로 초기화하지 않는다
    # for i in range(1, V + 1):
    #     dist[i][i] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

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

    return dist

dist = floyd_warshall(graph, V)
cycle = min([dist[i][i] for i in range(1, V + 1)])
print(cycle) if cycle != int(1e9) else print(-1)

---

접근 방법: 다익스트라 알고리즘

• 다익스트라 알고리즘도 특정 노드에서 다른 노드로 이어지는 최단 경로를 찾는 알고리즘이므로 사용할 수 있을 것 같았다.
• 다만, 다익스트라 알고리즘은 주어진 특정한 노드에서만 탐색하므로 노드의 갯수만큼 반복해야 최소길이 사이클을 찾을 수 있을것이다.

코드

# https://www.acmicpc.net/problem/1956
import heapq
import sys
from collections import defaultdict


INF = int(1e9)
input = sys.stdin.readline
V, E = map(int, input().split())
graph = defaultdict(list)
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))


# 다익스트라 알고리즘을 전체 노드 갯수만큼 반복문을 돌려서 최소값을 구하는 방법
# 시간 초과
def dijkstra(graph, start):
    dist = defaultdict(lambda: int(1e9))
    pq = [(0, start)]
    visited = set()

    # # 사이클을 체크해야하므로 시작지점을 0으로 초기화지 않음
    # dist[start] = 0

    while pq:
        acc, cur = heapq.heappop(pq)

        if acc > 0 and cur == start:
            return acc
        if cur in visited:
            continue
        visited.add(cur)

        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(pq, (cost, adj))

    return int(1e9)

cycle = int(1e9)
for i in range(1, V + 1):
    cycle = min(cycle, dijkstra(graph, i))
print(cycle) if cycle != int(1e9) else print(-1)

• 전체 노드만큼 반복문을 돌면서 다익스트라 알고리즘을 적용시켰는데, 시간초과가 되었다.

---

추가

• 플로이드-워셜 알고리즘은 시간복잡도가 $O(V^3)$이다. 여러 글들을 찾아보니 노드의 갯수가 수백단위를 넘어서면 백준이나 리트코드같이 런타임을 중요하게 체크하는 환경에서는 사용하기 힘들다고 한다.