[Python] LeetCode - 2492. Minimum Score of a Path Between Two Cities

LeetCode 2492번 Minimum Score of a Path Between Two Cities 문제는 그래프 탐색 문제다. 난이도는 Medium이며 DFS 등의 그래프 탐색 알고리즘을 통해 해결할 수 있다.

 

리트코드 2492번 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- Medium

 

문제 요약

• 1번부터 n번까지 n개의 도시가 주어진다.
• 두 도시 사이를 잇는 양방향의 도로의 점수 리스트가 주어진다. 모든 도시가 서로 꼭 이어져 있는 것은 아니다.
• 도시 1부터 도시 n까지 가는 경로에 있는 최소 점수를 구하라.
  • 지나간 도로를 다시 지나가도 된다.

 

문제 풀이 과정

• 지나간 도로를 다시 지나가도 되며, 지나갈 때마다 점수가 누적되는 방식이 아니라 그냥 최소 점수만 구하는 것이므로, 1번 도시에 이어진 모든 도로 중 최소 점수를 구하면 된다.
• DFS를 이용해 1번 도시에서부터 연결된 모든 노드를 탐색하면서, 각 노드에 연결된 모든 엣지의 점수를 확인하고 최소값을 저장한다.

코드

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        visited = [False for _ in range(n+1)]
        adj_dict = {k:list() for k in range(1, n+1)}
        for source, dest, score in roads:
            adj_dict[source].append((dest, score))
            adj_dict[dest].append((source, score))
        
        def dfs(here: int, ans: int):
            res = ans
						# 연결된 모든 엣지의 점수를 비교
            for next, score in adj_dict[here]:
                res = min(res, score)
                if not visited[next]:
                    visited[next] = True
                    res = min(res, dfs(next,res))
            return res
            
        visited[1] = True
        return dfs(1, float('inf'))

• 시간복잡도: O(n+m) (n: 도시 개수, m: 도로 개수)
• 공간복잡도: O(n+m) (n: 도시 개수, m: 도로 개수)