[백준] 1956 운동

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

특정 마을에서 운동을 출발하여, 다시 출발 마을로 돌아오는 길이 짧은 경우를 구해야 했습니다.

하나의 마을에서 출발하는 경우, 다익스트라를 이용하면 편리하지만 모든 마을에서 사이클이 존재하는지 확인이 필요하므로 플로이드 워셜 알고리즘을 이용하였습니다.

 

플로이드 워셜 알고리즘을 이용하여 모든 마을에서 최소 사이클을 한번에 구하도록 하였습니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

V, E = map(int, sys.stdin.readline().split())                                       # 마을, 도로 개수
distance = [[1e10] * V for _ in range(V)]                                           # 마을에서 다른 마을로 가는 최소 거리
answer = 1e10                                                                       # 최소 길이 사이클의 값

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    distance[a-1][b-1] = c                                                          # a 마을 ->  b 마을 거리

for k in range(V):
    for i in range(V):
        for j in range(V):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])   # i -> j 이동시, 서로 연결된 도로가 더 짧은지
                                                                                    # 다른 마을을 거쳐서 이동하는게 더 짧은지 비교 후 더 짧은 도로 선택

for i in range(V):                          
    answer = min(answer, distance[i][i])            # 출발지에서 다시 돌아오는 경우의 최소 도로 길이를 저장

print(answer if answer != 1e10 else -1)             # 사이클이 존재하지 않으면 -1 출력

---

🔗 문제 링크

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

1956번: 운동

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다