최단 경로 관리하기

문제

 

9370번: 미확인 도착지

 

1719번: 택배

 

---

 

재정의

• 택배택배 문제는 상대적으로 심플하다.
  A에서 B로 최단거리로 이동할려면 어느 노드로 가야하는지 구하면 된다.
  
  즉, 최단거리 갱신 타이밍에 가야할 노드도 갱신한다.

 

 

• 미확인 도착지
  주어지는 후보노드들의 최단 거리를 구했을 때, 특정 경로를 지나가는지 구하는 문제.
  일반적인 최단경로 알고리즘은 비용만을 관리한다.
  
  즉, 최단거리 갱신 타이밍에, 특정 경로 포함 여부를 갱신한다.

 

최단거리 알고리즘의 기본적인 흐름을 이해하고,

기본적인 흐름을 바탕으로 코드를 끼워넣어 원하는 결과를 얻어야 하는 문제이다.

 

---

 

용도 & 아이디어

보편적인 최단경로 문제에는 BFS, dijkstra, BellmanFord, FloydWarshall이 있다.

BFS는 노드간의 연결에 가중치가 없을 때 사용가능하다.

Dijkstra는 한 노드부터 나머지 노드로까지의 최단거리를 구할 때 사용한다.

BellmanFord와 FloydWarshall은 모든 노드로부터 나머지 노드로까지의 최단거리를 구할 때 사용한다.

 

가중치가 동일하다면, 노드간의 물리적 거리가 최단거리가 됩니다.

가중치가 동일하지 않다면? 비용이 적게 드는 거리가 최단거리가 됩니다.

 

B라는 노드의 최소비용을 10으로 알고 있었는데, 직접 와보니 8의 비용이 들었습니다.

그럼 어떤 가능성이 생길까 고민을 해 봅시다.

B와 연결된 모든 노드의 최소 비용또한 갱신 될 수 있다는 것을 의미 합니다.

 

Dijkstra 알고리즘은, 최소 비용의 전파를 통해 최단거리를 구합니다.

B라는 노드가 갱신되면, B와 연결된 노드들 또한 갱신할 기회는 주는 것과 같은 개념 입니다.

이 방식을 통해서 한 노드에서 나머지 노드까지의 최소 비용을 구할 수 있습니다.

 

모든 노드에서 모든 노드까지의 최소 비용은 경유지개념을 도입합니다.

시작, 경유, 끝 이 3가지 축으로 돌면서 더 짧은 경우를 갱신하여 모든 노드간을 파악할 수 있습니다.

 

---

 

FloydWarshall 경로 확인

택배문제에서 최단 경로를 위해 가야하는 노드를 관리해야 합니다.

최단 경로가 결정되는 부분은, 최단 경로를 업데이트 하는 부분 입니다.

그래서 최단 경로를 업데이트 하는 부분에 경로도 같이 갱신하면 되는 단순한 문제 입니다.

def flyod_washall(move_table: List[List[int]]) -> List[List[int]]:
    for mid in range(n):
        for st in range(n):
            for ed in range(n):
                new_cost = cost[st][mid] + cost[mid][ed]
                
                if new_cost < cost[st][ed]:
                    cost[st][ed] = new_cost
                    move_table[st][ed] = move_table[st][mid]
    
    return move_table

 

if문에서 최단 경로가 갱신됐다는 것은,

st -> ed 에서, mid를 거치는게 더 효율적이라는 말이 됩니다.

똑같이 st -> ed로 최소비용으로 갈려면 mid로 가야 한다는 말이 됩니다.

그래서 st -> ed 최소 비용 경로를 st -> mid 최소 비용 경로로 덮어쓰는 방식으로 경로를 관리할 수 있습니다.

 

---

 

최단 경로는 "비용"만 고려한다.

미확인 도착지를 풀면 뼈저리게 이 특성을 느낄 수 있다.

당연한 말이지만, 이 특성은 미확인 도착지를 풀 때 2가지 큰 이슈를 발생시킨다.

 

같은 비용은 갱신되지 않는다,

A라는 경로를 포함하는 최단 경로가 있는지 확인을 해야 하는데,

A를 포함하지 않는 경로로 10의 비용으로 완성 되었다고 가정하자.

A를 포함한 경로도 10의 비용을 가지는 방법을 찾더라도, 같은 비용이라 갱신되지 않는다.

 

그래서 같은 비용을 갱신할 수 있게 바꾸어야 하며,

A를 포함하지 않은 비용과 A를 포함한 비용이 같은 경우에는 갱신을 하도록 해야 한다.

 

동일 비용 갱신 시 inf == inf + inf 문제

무한 = 무한 + 무한 이다. 그래서 같은 비용의 갱신을 허용할 때 주의해야한다.

경로 두 개를 더한 것과 단일 경로를 같음을 판정할 수 있을 때, 무한이 들어간다면

우리의 예측에서 벗어나는 경우가 생길 수 있다.

 

def dijkstra(st_node: int) -> Dict[int, int]:
    minimum_cost = {node:[float('inf'), False] for node in range(nodes)}
    minimum_cost[st_node] = (0, False)
    next_node = [(0, st_node, False)]

    while next_node:
        cost, node, used = heappop(next_node)

        if cost > minimum_cost[node][0]:
            continue

        for new_node, new_cost in road_connect[node].items():
            tmp_used = used
            new_cost += cost

            if new_cost > minimum_cost[new_node][0]:
                continue

            if (node == road_st and new_node == road_ed)\
                    or (node == road_ed and new_node == road_st):
                tmp_used = True

            if minimum_cost[new_node][0] > new_cost:
                minimum_cost[new_node] = (new_cost, tmp_used)
                heappush(next_node, (new_cost, new_node, tmp_used))
            
            elif not minimum_cost[new_node][1] and tmp_used:
                minimum_cost[new_node] = (new_cost, tmp_used)
                heappush(next_node, (new_cost, new_node, tmp_used))
    
    return minimum_cost