백준 1956 - 운동

1956번: 운동 (acmicpc.net)

1956번: 운동

 

이 문제를 처음보고 solved.ac에서 본 그래프 문제들과 굉장히 유사한 문제라는 생각이 들게 되었다. 

그 문제들도 cost, start, end를 설정해서 list 형태로 append 시켜놓고, 알고리즘을 사용하게 되는데, 이 때 graph 알고리즘이라면 BFS, DFS 등이 있을 수 있겠지만, 나의 첫번째 접근은 "도로의 길이의 합이 최소"라는 지점에 착안하여 다익스트라 알고리즘을 사용했다.

 

◆ 나의 풀이 1

※ 다익스트라 알고리즘이란?

- 하나의 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘.

- 도착 노드 뿐만 아니라 모든 다른 노드까지 최단 경로로 방문하고, 각 노드까지의 최단 경로를 모두 찾게 된다.

- 매번 최단 경로의 노드를 선택하고 탐색을 반복하게 된다.

 

def dijkstra(start) :
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    
    while q :
        distance, node = heapq.heappop(q)
        if distance > dist[node] :
            continue
        
        for n in graph[node] :
            new_cost = n[1] + dist[node]
            if new_cost < dist[n[0]]:
                dist[n[0]] = new_cost
                heapq.heappush(q, (new_cost, n[0]))

 

일반적으로 이런식으로 작성하여 사용하게 된다.

1. 주로 heapq를 사용하여 구현

2. distance가 새로들어온 dist보다 짧으면 new_cost로 갱신을 하는 작업을 실시

 

이렇게 도로 길이 합의 최소를 구할 수 있게 된다.

 

 

import sys
input = sys.stdin.readline
import heapq
INF = sys.maxsize

v, e = map(int, input().split())
arr = [[] for _ in range(v+1)]
distance = [[INF] * (v + 1) for _ in range(v + 1)]
heap = []

# dist, 위치1, 위치2 순서로 heap에 push
for _ in range(e):
    a, b, c = map(int, input().split())
    arr[a].append([c, b])
    heapq.heappush(heap, [c, a, b])

while heap:
    dist, first, last = heapq.heappop(heap)
    if first == last:
        print(dist)
        break

    if distance[first][last] < dist:
        continue

    for i, j in arr[last]:
        # first -> last -> j
        n_distance = i + dist
        # (first->last->j vs first -> j) if more cheap, change n_distance
        if distance[first][j] > n_distance:
            distance[first][j] = n_distance
            heapq.heappush(heap, [distance[first][j], first, j])

 

이차원으로 distance 리스트를 변경시켜준 것과 first == last 일 때 끝까지 도착했으니, 거리를 print하고 break 하는 부분 외에는 사실 기본 알고리즘과 큰 차이가 없을 것이다. 이렇게 다익스트라 알고리즘을 사용해서 문제 풀이를 쉽게 끝내는 듯 했으나...

 

 

보다시피 엄청난 메모리 초과 폭풍을 만나게 되었다... 코드 내부를 조금이나마 가볍게 개선하려고 노력하다가 결국 포기한 마지막 코드가 위의 다익스트라 알고리즘 코드이다.

 

 

◆ 나의 풀이 2(정답)

 

결국 다익스트라 알고리즘 코드를 약 1시간 만에 포기하고, 새로운 알고리즘으로 접근하기로 했다. 내가 기존에 알고 있던 것은 다익스트라 알고리즘이 가장 효율적이라고 알고 있었는데, 그것도 그래프 마다 조금씩 다른 것 같았다.

다른 최소비용을 구할 수 있는 플루이드-워셜 알고리즘을 사용하게 되었다.

 

※ 플루이드-워셜 알고리즘이란?

- 모든 노드 사이의 최단 경로를 찾는 탐색 알고리즘.

1. 하나의 노드에서 다른 노드로 갈 수 없다면 INF로 배열에 값 저장, 갈 수 있다면 최소 비용.

2. 3중 for문을 이용하고, 거쳐가는 노드 설정 후 해당 정점을 거치는 동안 비용이 줄어든다면 갱신.

 

import sys
 
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
 
for x in range(1, n + 1):
    for y in range(1, n + 1):
        if x == y:
            graph[x][y] = 0
            break 
 
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
 
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
 
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b], end = " ")
    print()

 

참고할 만한 플루이드-워셜 구현체이다. 이것을 통해 우리 문제를 해결해보자.

 

 

import sys
input = sys.stdin.readline
INF = sys.maxsize

v, e = map(int, input().split())
distance = [[INF] * (v + 1) for _ in range(v + 1)]
for i in range(1, v+1):
    distance[i][i] = INF

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

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


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

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

 

이와 같이 구현할 수 있다. 알고리즘 자체를 사용하는 것에 있어, 어떤 알고리즘을 효율적으로 사용할 것이냐가 문제인 것이지, 알고리즘을 사용하게 되면 문제 해결을 하는 부분은 전혀 어렵지 않은 문제 였다.

 

결국 플루이드-워셜로 바로 정답을 받게 되었다. GLB Algorithm Study 원들과 주말간에 토론을 통해 어떤 상황에 어떤 알고리즘을 쓰는 것이 효과적인지를 명확히 알고 지나가야겠다는 생각으로 이번주 문항은 1956번 운동으로 선정했다.