[BOJ] 1956 운동 (Python3)

문제

V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.

당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.

도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

정답 코드

v, e = map(int, input().split())
INF = int(1e9)

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

for i in range(e):
    a, b, d = map(int, input().split())
    graph[a][b] = d


for k in range(1, v + 1):
    for a in range(1, v + 1):
        for b in range(1, v + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
answer = INF
for i in range(v + 1):
    answer = min(answer, graph[i][i])
    
if answer == INF:
    print(-1)
else:
    print(answer)

문제 풀이

처음에는 사이클이 나왔길래 유니온파인드를 쓰는 건가? 했는데, 생각해보니까 유니온 파인드로는 사이클만 잡아낼 수 가 없었다.

그러다 V의 최대범위가 400이길래 얼추 400 * 400 으로도 시간복잡도가 충분하다 싶어서 dfs로 풀이해보았는데, 생각해보니까 dfs의 경우 노드별 간선개수에 따라 시간복잡도가 n^2을 넘어갈 수 있기 때문에 recursionError가 발생했다.

따라서 어떤 알고리즘을 써야할지 찾아보았는데, 플로이드-워셜 알고리즘을 사용하는 것이었다.

이름만 들어봤지 처음 써보는 알고리즘이었는데, 사용해보니까 다익스트라의 브루트 포스 버젼의 알고리즘이었다. 출발지 경유지 도착지 3가지의 경우의수의 노드 최소거리를 모두 구해주기 때문에 n^3으로 현재 문제는 얼추 32,000,000이므로 1억이 넘지 않아 통과할 수 있지만, 상대적으로 느린 알고리즘이다.

어쨌든 이차원배열을 무한으로 초기화 해준뒤, 플로이드-워셜 알고리즘을 적용하여 모든 간선의 경우의수를 구해주면 된다.

다익스트라 변형 코드

사실 다익스트라의 경우가 플로이드-워셜보다 시간복잡도가 적기 때문에 자기 자신에서 자신으로의 거리만 구할 수 있게하면 훨씬 빠르겠다 싶었는데, 구글링 해보니 실제로 다익스트라를 변형하여 풀이한 코드가 있어서 첨부한다.

여기서는 기존의 일차원 배열을 사용하던 다익스트라를 2차원으로 변형하여 사용했다.

출처 링크 - nkrang님 블로그

import heapq as hq

V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
#거리를 저장할 배열을 2차원으로
dist = [[1e9] * (V+1) for _ in range(V+1)]

heap = []
for _ in range(E):
    x, y, c = map(int, input().split())
    graph[x].append([c, y])
    dist[x][y] = c
    #heap에도 비용, 출발지, 도착지 3개의 값을 넣어준다.
    #유효한 경로 값을 다 넣어줌
    hq.heappush(heap, [c, x, y])


while heap:
    #최소 비용의 경로를 먼저 뽑아주고 (d:비용, s:출발, g:도착)
    d, s, g = hq.heappop(heap)
    #출발지와 도착지가 같다면 사이클!
    #heap을 이용하기 때문에 처음 나온 사이클이 가장 비용이 작은 사이클이므로 break 해버려도 됨! -> 여기서 시간이 굉장히 절약되는 듯 
    if s == g:
        print(d)
        break
    #d 값이 이미 저장된 비용보다 크다면 넘겨버림
    if dist[s][g] < d:
        continue
        
    #g에서 갈 수 있는 노드들을 검사
    for nd, ng in graph[g]:
    	# s->g->ng로 가는 비용
        new_d = d + nd
        # s->g->ng로 가는게 s->ng보다 빠르다면 값 갱신해주고 heap에 넣어줌
        if new_d < dist[s][ng]:
            dist[s][ng] = new_d
            hq.heappush(heap, [new_d, s, ng])
else:
    #heap 다 돌았는데 없다면 -1
    print(-1)