코드

# v : 마을 개수
# e : 도로 개수
v, e = map(int, input().split())

INF = int(1e9)

# 플로이드 워셜 사용 => 입력 받을 그래프 자체를 INF로 초기화
graph = [[INF for _ in range(v+1)] for _ in range(v+1)]

# 도로의 정보 입력
for _ in range(e):
    a, b, c = map(int, input().split())
    
    # 같은 도로가 주어지는 경우는 없으므로
    # 그냥 입력
    graph[a][b] = c

# 플로이드 워셜 구현
def floyd():
    for k in range(1, v+1):
        for a in range(1, v+1):
            for b in range(1, v+1):

                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
                
floyd()   

# 최단 사이클의 길이를 담을 변수
result = INF

# i -> i로 가는 도로 길이 (싸이클)의 최솟값을 result에 담음
for i in range(1, v+1):
    result = min(result, graph[i][i])
    
# result == INF => 사이클이 불가능한 경우 -1 출력
if result == INF:
    print(-1)
else:
    print(result)

문제 해설

플로이드 워셜 알고리즘을 이용하여 푸는 문제.

출발지에서 도로를 달려서 다시 출발지로 돌아오는 최단 거리를 구하는 문제이다. 즉, 싸이클이 존재하는 그래프가 주어진다는 의미!!! 지도의 정보를 입력받을 때, 자기 자신으로 돌아오는 경우를 별도로 처리해주지 않고 플로이드 워셜을 적용시킨 후, 그래프의 대각선에 위치하는 값들(자기 자신으로 돌아오는 가중치 => 싸이클) 중 최솟값을 출력하면 정답으로 인정된다.

플로이드 워셜은 다익스크라에 비해서 구현 난이도가 상당히 쉬운 편이므로 잘 숙지하고 이용해야겠다.

댓글남기기

참고