백준 1956 운동 문제풀이

문제 

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

1956번: 운동

 

 

문제 접근 방식

특정 지점에서 시작해서 다른 지점을 찍고 다시 시작 위치로 돌아오는 최단 거리를 구하는 문제이다. 가중치가 있는 그래프의 최단 경로를 구하는 알고리즘인 다익스트라, 벨만포드, 플로이드 워셜을 배우긴 했으나, 세 알고리즘 모두 다른 위치로의 최단 거리를 구한는 문제여서 처음 이 문제를 봤을 때 당황스러웠다. 

 

 

그래도 배운 것 내에서 나온다는 생각을 가지고 세 알고리즘을 활용하려 했다. 아래의 사고 과정을 통해서 문제를 접근했다.

 

첫 번째,

일단, 특정 노드 s를 시작점으로 가정하고 문제를 풀었다. 끝점을 v라고 했을 때, s > v 로 최단 경로로 이동하고, v > s 로는 일반 간선 길이를 더해서, 각 노드마다 해당 값을 구해서 그 중 최단 거리를 반환하는 방식이다. 이렇게 진행할 경우, v > s 의 값이 최단 경로를 보장하지 못하기 때문에 이 방식은 오답이 나오게 될 것이다.

 

두 번째,

v > s 의 일반 간선의 길이가 최단 경로를 보장하지 못하기 때문에, v > s 의 최단 경로를 구해서 더해주면 된다. 즉, 시작 노드 s와 특정 노드 v에 대해 [ s > v 로의 최단 거리] + [ v > s 로의 최단 길이 ] 를 더해서, 그 값들 중 비교를 통해 최솟값을 구하면 사이클의 최단 경로를 구할 수 있다.

 

모든 노드가 시작점이 될 수 있기 때문에 플로이드 워셜 알고리즘을 사용하여 [ 모든 노드 > 모든 노드 ] 로의 최단 길이를 구하고, 이를 가지고 모든 노드 s,v 에 대해 [ s > v 로의 최단 거리] + [ v > s 로의 최단 길이 ] 를 비교하여 최솟값을 구한다.

 

 

시간 복잡도

플로이드 워셜 알고리즘의 시간 복잡도가 O(n^3) 이며, 최솟값을 구하는데 시간 복잡도가 O(n^2) 이기 때문에 전체적인 시간복잡도는 O(n^3) 이다. V의 최댓값이 400이므로 시간 내에 동작할 수도 있을 것 같다..! ( 이 방법으로 진행시 python으로는 시간 초과가 나고, pypy3로는 통과가 된다. 다른 방법도 찾아봐야함)

 

 

코드

import sys
input=sys.stdin.readline

INF=int(1e9)

if __name__=='__main__':
    v,e=map(int,input().split())

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

    for i in range(1,v+1):
        adj[i][i]=0

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

    # 모든쌍 -> 모든쌍으로의 최소 거리를 구한다.
    for k in range(1,v+1):
        for i in range(1,v+1):
            for j in range(1,v+1):
                adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
    # adj[i][j] +adj[j][i] = i > j > i , 즉 자기 자신으로 돌아오는 최소 길이를 구한다.
    answer=INF
    for i in range(1,v+1):
        for j in range(1,i):
            answer=min(answer,adj[i][j]+adj[j][i])


    if answer==INF:
        answer=-1

    print(answer)

 

 

회고

우선 순위 큐를 활용하여 시간을 단축 시킨 다익스트라 응용방법도 있는데 공부가 필요하다..