[BOJ] 백준 1956번 운동 | python 파이썬 코드, 해설, 풀이

백준 1956번 운동 문제 파이썬 풀이입니다.
1956번: 운동 (acmicpc.net)

문제 자체는 짧고 간단합니다.
'가중치가 있는 유향그래프에서 가장 작은 사이클을 찾아라' 로 요약할 수 있겠습니다.

 

처음에 다익스트라 문제로 착각하여 삽질을 좀 했는데, 아래와 같이 코드를 짰을 때 반례가 생겼다.
 

틀린코드

       from collections import deque
      

       INF = float('inf')
      

       v, e = map(int, input().split())
      

        
      

       graph = [[] for _ in range(v+1)]
      

        
      

       for _ in range(e):
      

           a, b, c = map(int, input().split())
      

           graph[a].append([b, c])
      

        
      

       queue = deque()
      

        
      

       result = INF
      

       for start_node in range(1, v+1):
      

           queue.append([start_node, 0])
      

           distance = [INF] * (v+1)
      

           distance[start_node] = 0
      

        
      

           while (queue):
      

               now_node, now_cost = queue.popleft()
      

               if (now_cost > distance[now_node]):
      

                   continue
      

               for next_node, next_cost in graph[now_node]:
      

                   if (next_node == start_node):
      

                       result = min(result, now_cost+next_cost)
      

                       continue
      

                   if (distance[next_node] > now_cost+next_cost):
      

                       distance[next_node] = now_cost+next_cost
      

                       queue.append([next_node, next_cost])
      

       print(result)
      

        
      

 
반례 -> 답 3  | 결과 2

4 5
1 2 1
2 3 1
3 4 1
4 2 1
2 1 100

 
 
본 문제는 플로이드-워셜 알고리즘으로 풀 수 있다. N이 400이기 때문에 O(N^3) 시간 복잡도를 가지는 알고리즘으로도 시간내에 통과할 수 있다.
 

정답코드

       INF = float('inf')
      

       n, m = map(int, input().split())
      

       graph = [[INF]*(n+1) for _ in range(n+1)]
      

        
      

       for _ in range(m):
      

           src, dst, cost = map(int, input().split())
      

           graph[src][dst] = cost
      

        
      

       for k in range(1, n+1):
      

           for i in range(1, n+1):
      

               for j in range(1, n+1):
      

                   graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
      

        
      

       result = INF
      

       for i in range(1, n):
      

           result = min(result, graph[i][i])
      

       if (result == INF):
      

           print(-1)
      

       else:
      

           print(result)
      

        
      

이때 주의해야할 점은 해당 문제는 사이클만 고려하고, 노드가 1개인 사이클은 형성할 수 없기 때문에 일반적인 플로이드-워셜 문제와 다르게 line10에 graph[k][k]를 0으로 초기화 하는 코드를 넣지 않는다.
 
그러면 graph 배열의 대각이 다른 노드 k를 거쳐서 온 사이클의 누적값을 저장하게 되고, 마지막에 대각의 값만 비교해주면 정답을 구할수있다.
이때 주의할점은 대각이 모두 INF(초기값)이면 사이클이 없다는 의미임으로 -1을 출력한다.

4트 끝에 맞출 수 있었습니다.