[python code review] 7주차 (최단경로, 궁금한 민호, 웜홀)

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

1753번: 최단경로

import heapq

V, E = map(int, input().split())
k = int(input())
graph = [[] for _ in range(V+1)]
distance = [1e9 for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))


def dijkstra(start):
    distance[start] = 0
    queue = []
    heapq.heappush(queue, [0, start])
    while queue:
        cost, now = heapq.heappop(queue)
        if distance[now] < cost:
            continue
        for next_cost, next_node in graph[now]:
            weight = next_cost + cost
            if weight < distance[next_node]:
                distance[next_node] = weight
                heapq.heappush(queue, [weight, next_node])

    for i in range(1, V+1):
        if distance[i] == 1e9:
            print('INF')
        else:
            print(distance[i])

            
dijkstra(k)

heapq로 푸는 접근 방법은 떠올랐는데

start부터 각 노드까지의 최소 비용을 distance 배열로 저장하는 방법을 까먹었다 (;;)

참고하기 좋은 블로그 https://ujin-dev.tistory.com/35

 

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

1507번: 궁금한 민호

n = int(input())
graph = [[0]*(n+1)]
deactivated = [[False]*(n+1) for _ in range(n+1)]

for i in range(n):
    graph.append([0] + list(map(int, input().split())))

# 거쳐가는 점
for k in range(1, n+1):
    # 시작점
    for a in range(1, n+1):
        # 끝점
        for b in range(1, n+1):
            if a == b or a == k or b == k:
                continue
            if graph[a][b] == graph[a][k] + graph[k][b]:
                deactivated[a][b] = True
            elif graph[a][b] > graph[a][k] + graph[k][b]:
                print(-1)
                exit()

total = 0
for a in range(1, n+1):
    for b in range(a, n+1):
        if not deactivated[a][b]:
            total += graph[a][b]
print(total)

플로이드 워셜 알고리즘을 이용하여 접근하면 된다.

플로이드 워셜 알고리즘 ->  https://www.youtube.com/watch?v=hw-SvAR3Zqg

플로이드 워셜 알고리즘은 임의의 노드 k를 이용해 a부터 b까지의 최단 경로를 구하는 방법을 제공한다.

이 점화식은 다음과 같다.

Dab = min(Dab, Dak + Dkb)    -- > Dab: a부터 b까지의 거리 

만약에 Dab와 Dak+Dkb가 같다면 이는 a와 b는 간접 경로를 통해 이동할 수 있다는 뜻이다. 따라서 a와 b를 연결짓는 간선은 제거해줄 수 있다. 간선 제거를 위해 사용되는 배열이 deactivated이다.

그리고 Dab가 Dak+Dkb보다 크다면 이는 Dab는 a부터 b까지의 최단 경로라는 조건에 어긋난다.

따라서 이러한 경우에는 -1을 출력해준다.   

 

 

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

1865번: 웜홀

def bellman(start):
    distance[start] = 0

    for i in range(1, n+1):
        for j in range(1, n+1):
            for nxt, time in graph[j]:
                # 현재 노드를 거쳐서 이동하는 경우가 더 짧을 경우 
                if distance[nxt] > distance[j] + time:
                    distance[nxt] = distance[j] + time
                    # n번 이후에도 값이 갱신되면 음수 사이클 존재
                    if i == n:
                        return True
    return False


for _ in range(1, int(input())+1):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    distance = [1e9 for _ in range(n + 1)]
    for _ in range(m):
        s, e, t = map(int, input().split())
        graph[s].append([e, t])
        graph[e].append([s, t])
    for _ in range(w):
        s, e, t = map(int, input().split())
        graph[s].append([e, -t])

    negative_cycle = bellman(1)
    if not negative_cycle:
        print("NO")
    else:
        print("YES")

벨만 포드 알고리즘을 이용하는 전형적인 문제이다. 

유사 문제 -> 백준 타임머신 https://www.acmicpc.net/problem/11657

11657번: 타임머신

벨만포드 알고리즘 개념 -> https://www.youtube.com/watch?v=Ppimbaxm8d8