[백준] 1956번 운동(python)

 

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

 

1956번: 운동

 

 

1. 난이도 골드4 (🥇)

 

2. 문제 해결 과정 (보완 필요해서 4번에 추가해놨음)

사이클을 이루는 도로를 찾기 위해서는

 

1. 플로이드 워셜 알고리즘을 이용해 모든 지점에서 다른 지점까지의 최단 경로를 구한다.

2. 출발 장소 -> 도착장소 , 도착장소 -> 출발장소로 가는 두 경로 모두 INF가 아닐 경우의 값 중 최솟값을 구한다.

(cycle이 이뤄지지 않았을 경우엔 둘 중 하나 이상의 값이 INF이다.)

 

위의 두 과정을 거치면 된다.

이때, 같은 장소에서 출발하고 도착해도 CYCLE로 취급되기 때문에 출발지점과 도착지점이 같은 경우는 제외시키면 된다.

 

 

3. 내가 제출한 코드

import sys
input = sys.stdin.readline

INF = int(1e9)

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

dist = [[INF] * (v+1) for _ in range(v+1)]

for i in range(1,v+1):
  for j in range(1,v+1):
    if i == j:
      dist[i][j] = 0

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

for k in range(1,v+1):
  for i in range(1,v+1):
    for j in range(1,v+1):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

result = INF

for i in range(1,v+1):
  for j in range(1,v+1):
    if i != j and dist[i][j] != INF and dist[j][i] != INF:
      result = min(result, dist[i][j]+dist[j][i])

if result != INF:
  print(result)
else:
  print(-1)

 

4. 추가

내가 작성한 코드는 자신에게서 출발해서 자신으로 돌아오는 부분을 다 0으로 설정해놓았다.

 

그러나 이 문제에서 dist[i][i]가 INF가 아닌 값이라면 cycle이 돌고 있다는 소리이다. 

 

(=> i에서 출발해서 cycle을 돌고 온 후 i로 도착한 값이기 때문이다.)

 

dist[i][i] 값 중 최솟값을 출력하면 된다.

 

INF = int(1e9)

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

dist = [[INF] * (v+1) for _ in range(v+1)]

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

for k in range(1,v+1):
  for i in range(1,v+1):
    for j in range(1,v+1):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

result = INF

for i in range(1,v+1):
  result = min(result, dist[i][i])

if result != INF:
  print(result)
else:
  print(-1)

 

 

 

 

cycle이 없을 경우 -1을 출력한다는 조건을 적지 않고 제출해서 틀렸었ㄷㅏ ㅎㅎ..