[백준 22868번] 파이썬 - 산책(small)

시간 제한 1초, 메모리 제한 1024MB

# 조건

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.

현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 $E$에서 $S$로 올 때 $S$에서 $E$로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 $S$에서 $E$로 가는 가장 짧은 거리와 $E$에서 $S$로 가는 가장 짧은 거리를 원한다.

정점 $S$에서 정점 $E$로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 $S$에서 정점 $E$로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 가장 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리($S$에서 $E$로 가는 거리 + $E$에서 $S$로 가는 거리)를 구해보자.

# 접근 방법

• 출발지에서 목적지에 도착한 후 다시 출발점으로 돌아오는 최소의 경로를 구하면 되기에 2번의 다익스트라를 활용하여 풀어주었다.
• 이 때 주의할 점은 출발지에서 목적지로 가는 최소 경로가 여러 개인 경우 경유하는 정점의 번호가 사전순으로 빠른 길을 선택하면 된다.
  • 이 작업을 위해서 각 노드들의 연결 관계를 sort로 정렬해주었다.
• 이후 다익스트라 함수를 수행해주는데 출발지에서 목적지로 가는 첫 번째 행동의 경우 dist[st]를 0으로 만들고, S와 E를 그대로 넣어준다.
  • 또한, Q에는 **누적 가중치, [현재까지의 경로]를 넣어준다.
• 도착지에 도착했다면 RETURN 받은 비용을 result에 더해주고, dist 배열을 초기화, route에 표시된 곳을 0으로 변경해준 후 E와 S를 반대로 넣어 다시 수행해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  

def dijkstra(st, en):  
    q = []  
    heappush(q, [0, [st]])  
    while q:  
        val, route = heappop(q)  
        if route[-1] == en:  

            return val, route  
        if dist[route[-1]] < val:  
            continue  

        for n in node[route[-1]]:  
            if dist[n] > val + 1:  
                heappush(q, [val+1, route + [n]])  
                dist[n] = val+1  


N, M = map(int, input().split())  
node = [[] for _ in range(N+1)]  

for _ in range(M):  
    a, b = map(int, input().split())  
    node[a].append(b)  
    node[b].append(a)  

for i in range(N+1):  
    node[i].sort()  

S, E = map(int, input().split())  
result = 0  
dist = [float('inf')] * (N + 1)  
r = []  
for i in range(2):  
    if i == 0:  
        dist = [float('inf')] * (N + 1)  
        dist[S] = 0  
        v, r = dijkstra(S, E)  
        result += v  

    else:  
        dist = [float('inf')] * (N + 1)  
        for j in r:  
            dist[j]= 0  
        dist[E] = 0  
        dist[S] = float('inf')  
        v,r = dijkstra(E, S)  
        result += v  

print(result)