[백준 / 1504] 특정한 최단 경로 - Python

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

1504번: 특정한 최단 경로

<풀이>

지나야 하는 두 점 v1과 v2을 거쳐서 1에서 N으로 가야 한다. 따라서 나올 수 있는 경로는

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

이 두가지이다. 이 둘을 비교하여 더 짧은 거리가 정답이다.

 

해당 문제는 다익스트라 알고리즘(Dijkstra Algorithm)을 선행해야 한다.

 

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

 

<입력>

 

N, E = map(int, sys.stdin.readline().split())
graph = {i: [] for i in range(1, N+1)}

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())

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

v1, v2 = map(int, sys.stdin.readline().split())

 

노드의 개수 N과 간선의 개수 E를 입력받는다.

노드는 1 ~ N까지 있으므로 해당 개수만큼 그래프를 선언한다.

 

간선의 개수만큼 입력이 된다. 양방향이므로 입력받는 a와 b점에서 서로의 방향으로 그래프를 추가한다.

 

반드시 지나야하는 점 v1과 v2를 입력받는다.

<연산>

case1 = dijkstra(graph, 1)[v1]+dijkstra(graph, v1)[v2]+dijkstra(graph, v2)[N]
case2 = dijkstra(graph, 1)[v2]+dijkstra(graph, v2)[v1]+dijkstra(graph, v1)[N]

answer = case1 if case1 < case2 else case2

if answer == float('inf'):
    answer = -1

print(answer)

 

풀이에 적은 두가지 경로를 계산하여 case1과 case 2에 넣는다 더 작은 수가 정답이 된다.

만약 가는길이 없는 경우 dijkstra알고리즘에서 'inf'값이 나오므로 해당 경우는 -1로 치환하여 출력한다.

<알고리즘>

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}

    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        curDistance, curNode = heapq.heappop(queue)

        if curDistance > distances[curNode]:
            continue

        for newNode, newDistance in graph[curNode]:
            distance = curDistance + newDistance

            if distance < distances[newNode]:
                distances[newNode] = distance
                heapq.heappush(queue, [distance, newNode])

    return distances

다익스트라 알고리즘을 구현한다.

 

거리는 갱신되므로 최댓값으로 설정한다.

시작 노드의 값을 0으로 설정하고 queue에 넣는다.

 

queue에 값이 없을 때 까지 while문을 반복한다.

받아온 값이 distances에 있는 값보다 크면 해당 값은 생략한다.

 

graph에 연결된 노드와 값을 받아와서 다음 거리의 값을 계산한다.

기존에 있떤 distances의 값보다 작으면 값을 경신하고 queue에 넣어준다.

<전체 코드>

import heapq
import sys

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}

    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        curDistance, curNode = heapq.heappop(queue)

        if curDistance > distances[curNode]:
            continue

        for newNode, newDistance in graph[curNode]:
            distance = curDistance + newDistance

            if distance < distances[newNode]:
                distances[newNode] = distance
                heapq.heappush(queue, [distance, newNode])

    return distances


N, E = map(int, sys.stdin.readline().split())
graph = {i: [] for i in range(1, N+1)}

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())

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

v1, v2 = map(int, sys.stdin.readline().split())

case1 = dijkstra(graph, 1)[v1]+dijkstra(graph, v1)[v2]+dijkstra(graph, v2)[N]
case2 = dijkstra(graph, 1)[v2]+dijkstra(graph, v2)[v1]+dijkstra(graph, v1)[N]

answer = case1 if case1 < case2 else case2

if answer == float('inf'):
    answer = -1

print(answer)