난이도 : 골드 4
유형 : 최단경로
https://www.acmicpc.net/problem/1956
문제 접근
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다.
-> 노드 : V, 간선 : E
도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.
마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
-> 단방향 간선, 노드 1번~V번
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다.
운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
-> 최소합으로 사이클 찾기
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오.
두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.
예제 입력 1을 그래프로 표현하면 다음 그림과 같다.
이때 해답인 최소 사이클은 2와 3을 왕복하는 거리인 1+2인 3이 된다.
이 문제는 모든 정점 쌍 간의 최단 거리를 구하고,
그 중에서 i → j → i가 가능한 사이클 중에서
최단 사이클의 길이를 구하는 문제이기에
이런 모든 정점 쌍 간 거리를 구하는 데에는 3중 포문을 통해 모든 최단거리를 배열에 저장하는 플로이드-워셜이 적합하다.
플로이드를 이용해서 dist[i][j] 를 다 구한 후, dist[i][i] 가 0보다 큰 경우가 사이클이 된다.
해답 및 풀이
import sys
input = sys.stdin.readline
INF = int(1e9)
V, E = map(int,input().split())
distance = [[INF]*(V+1) for _ in range(V+1)]
for _ in range(E):
a, b, c = map(int,input().split())
distance[a][b] = min(distance[a][b],c)
# 플로이드-워셜
for k in range (1, V + 1):
for i in range(1, V + 1):
for j in range(1, V + 1):
if distance[i][j] > distance[i][k] + distance[k][j]:
distance[i][j] = distance[i][k] + distance[k][j]
# 사이클 중 최소값 찾기
answer = INF
for i in range(1, V + 1):
if distance[i][i] < answer:
answer = distance[i][i]
print(answer if answer != INF else -1)핵심 코드는 if distance[i][i] < answer : 이다.
i부터 i까지의 최소거리가 INF보다 작다면, 즉 갱신이 되었다면 이는 사이클이 있다는 뜻이므로 가장 작은 answer로 갱신해준다.
python3 로 제출 시 시간초과가 나고 pypy3으로 제출하면 통과한다.
python3으로 통과하고 싶다면 다익스트라 알고리즘 + for문으로 모든 노드의 최단거리를 저장하고 푸는 방법이 있지만 시도하지는 않았다.
