[백준] 9370번 미확인 도착지 _ Python

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

9370번: 미확인 도착지

 

 

---

 

1. Preview

시간 복잡도: O(3(V+E))

 

공간 복잡도: O(N)

 

참고

https://frog-in-well.tistory.com/68

https://ddingmin00.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-9370%EB%B2%88-%EB%AF%B8%ED%99%95%EC%9D%B8-%EB%8F%84%EC%B0%A9%EC%A7%80

 

 

유형: 다익스트라

 

 

---

 

2. 초기 접근 방법

문제에서 핵심적으로 사용해야 하는 것은

"출발지 / 목적지 후보 리스트 / 반드시 지나가는 g-h 교차로" 이다.

 

'그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다' 로 문제에서 제시했기 때문에

다익스트라로 최단 목적지까지 최단거리로 이동 후, 해당 노선에서 g-h 교차로를 지나가는지 판단했다.

# distance[i][0] : s에서 i번째 노드까지 가는데 걸리는 최소 비용
# distance[i][1] : s에서 i번째 노드까지 가는데 걸리는 경로

distance[next_node][0] = distance[now][0] + next_dist
distance[next_node][1] = distance[now][1] + str(now) # 지나온 노드

 

 

위 풀이법은 최단거리로 이동 했을 때, g-h 교차로를 지나가는지를 판단하는 것이다.

하지만 s(출발지)에서 e(목적지)까지의 최단경로가 2개 이상일 시 문제가 발생한다.

1) g-h 교차로를 지나가는 최단경로

2) g-h 교차로를 지나가지 않는 최단경로

 

다익스트탐색 순서에 따라서 g-h 교차로를 지나가지 않는다고 판단할 수도 있으므로, '경로비교'가 아닌 '비용비교'로 판단을 해야 한다.

 

 

---

 

3. 생각

 

그러기 위해서는 직관적으로 다익스트라 알고리즘을 3번 탐색하면 된다.

 

1) s(출발지) 중심으로 모든 최단경로를 구하는 다익스트라 (s→g / s→h)

2) g(교차로) 중심으로 모든 최단경로를 구하는 다익스트라 (g→e)

3) h(교차로) 중심으로 모든 최단경로를 구하는 다익스트라 (h→e)

 

이 때 g / h 어느 노드를 먼저 탐색해야 효율적인지 모르므로,  2가지 경우를 비교해서 최솟값을 찾으면 된다.

# (s → g → h → c) , (s → h → g → c)
minS = min(distFromS[g] + gToh + distFromH[c], distFromS[h] + gToh + distFromG[c])

# 기존 최단거리에서 g-h 교차로를 지나갔음을 의미한다..
if K == minS:
    result.append(c)

 

 

 

다익스트라 2번 탐색으로 문제를 해결할 수도 있다.

1) s(출발지) 중심으로 모든 최단경로를 구하는 다익스트라 (s→g / s→h)

2) s→g / s→h 중 더 짧은 노드 중심으로 모든 최단경로를 구하는 다익스트라 (middle→e)

distFromS = dijkstra(s)

    if distFromS[g] > distFromS[h]:
        middle = g
    elif distFromS[g] < distFromS[h]:
        middle = h
    distFromMiddle = dijkstra(middle)

    result = []
    for c in candidates:
        # s → c
        K = distFromS[c]

        # (s → g → h → c) , (s → h → g → c)
        Q = distFromS[middle] + distFromMiddle[c]

        # 기존 최단거리에서 g-h 교차로를 지나갔음을 의미한다..
        if K == Q:
            result.append(c)

 

 

---

 

4. 코드

 

1) 다익스트라 3번 탐색 (308ms)

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)

def dijkstra(start):
    distance = [INF for _ in range(N + 1)]
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        # 기존 저장되어 있는 것이 더 작다면
        if distance[now] < dist:
            continue

        for next_dist, next_node in graph[now]:
            if distance[next_node] > distance[now] + next_dist:
                distance[next_node] = distance[now] + next_dist
                heapq.heappush(pq, (distance[next_node], next_node))

    return distance


T = int(input())
for _ in range(T):
    # 교차로, 도로, 목적지 후보의 개수
    N, M, t = map(int, input().split())

    # 범인 출발 위치, g와 h 사이 지나감
    s, g, h = map(int, input().split())

    # 도로 그리기
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((c, b))
        graph[b].append((c, a))

        if (a == g and b == h) or (a == h and b == g):
            gToh = c

    # 목적지 후보 리스트
    candidates = [int(input()) for _ in range(t)]

    distFromS = dijkstra(s)
    distFromG = dijkstra(g)
    distFromH = dijkstra(h)

    result = []
    for c in candidates:
        # s → c
        K = distFromS[c]

        # (s → g → h → c) , (s → h → g → c)
        minS = min(distFromS[g] + gToh + distFromH[c], distFromS[h] + gToh + distFromG[c])

        # 기존 최단거리에서 g-h 교차로를 지나갔음을 의미한다..
        if K == minS:
            result.append(c)

    result.sort()
    print(*result)

 

 

2) 다익스트라 2번 탐색 (284ms)

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
def dijkstra(start):
    distance = [INF for _ in range(N + 1)]
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        # 기존 저장되어 있는 것이 더 작다면
        if distance[now] < dist:
            continue

        for next_dist, next_node in graph[now]:
            if distance[next_node] > distance[now] + next_dist:
                distance[next_node] = distance[now] + next_dist
                heapq.heappush(pq, (distance[next_node], next_node))

    return distance


T = int(input())
for _ in range(T):
    # 교차로, 도로, 목적지 후보의 개수
    N, M, t = map(int, input().split())

    # 범인 출발 위치, g와 h 사이 지나감
    s, g, h = map(int, input().split())

    # 도로 그리기
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((c, b))
        graph[b].append((c, a))

        if (a == g and b == h) or (a == h and b == g):
            gToh = c

    # 목적지 후보 리스트
    candidates = [int(input()) for _ in range(t)]

    distFromS = dijkstra(s)

    if distFromS[g] > distFromS[h]:
        middle = g
    elif distFromS[g] < distFromS[h]:
        middle = h
    distFromMiddle = dijkstra(middle)

    result = []
    for c in candidates:
        # s → c
        K = distFromS[c]

        # (s → g → h → c) , (s → h → g → c)
        Q = distFromS[middle] + distFromMiddle[c]

        # 기존 최단거리에서 g-h 교차로를 지나갔음을 의미한다..
        if K == Q:
            result.append(c)

    result.sort()
    print(*result)