(Python3) - LeetCode (Medium) : 2924. Find Champion II

https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i

dijkstra문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 인접리스트 형태로 map edges선언 후 key에는 node번호, value에는 현 node에 연결된 node들을 배열로 저장합니다.

 

2. 각 query별 최소거리 배열 distances 선언 후 빈 배열로 초기화합니다.

📔 풀이과정

n이 500이므로 O(n^3)의 시간복잡도로 가진 알고리즘은 사용할 수 없습니다. 단순 bfs나 플로이드 와샬을 사용한다면 시간초과가 뜹니다. 따라서 시간복잡도가 O((V+E)log(E))인 dijkstra를 사용해 해결합니다.

 

1. dijkstra를 구현합니다.

 

1-1. heap자료구조 pq를 선언 후 (거리, 현재노드)를 tuple형태로 heappush합니다.

 

1-2. 각 node별 최소 거리 distances를 선언 후 n개 방의 원소를 각각 최댓값인 0x3f3f3f3f(약 10억)으로 초기화해줍니다.

 

1-3. pq에 원소가 존재하는 동안 while loop를 수행하며 도착했다면 해당 거리를 반환해주고 현 노드의 거리가 기존에 저장된 distances거리와 비교해 거리를 갱신해주고 heap에 push해줍니다. 

 

2. 각 query별 loop를 수행하며 dijkstra의 반환값을 distances에 저장해줍니다.

📔 정답 출력 | 반환

distances를 반환합니다.

---

📕 Code

📔 Python3

from heapq import heappop, heappush
class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        def dijkstra(edges, end):
            pq = []
            distances = [0x3f3f3f3f] * n
            distances[0] = 0
            heappush(pq, (0,0))
            while pq:
                distance, node = heappop(pq)
                if node == end:
                    return distance
                if distance > distances[node]:
                    continue
                
                for next_node in edges[node]:
                    if distance + 1 < distances[next_node]:
                        distances[next_node] = distance + 1
                        heappush(pq, (distances[next_node], next_node))
            return -1

        edges = {i: [i+1] for i in range(n)}
        distances = []
        for q in queries:
            edges[q[0]].append(q[1])
            distances.append(dijkstra(edges, n-1))
        return distances

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.