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

- Problem

2492. Minimum Score of a Path Between Two Cities

- 내 풀이 1 (BFS)

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        def bfs(start_node):
            minimum_score = float('inf')
            q = deque([start_node])
            visited = set()
            visited.add(start_node)

            while q:
                cur = q.popleft()

                for wei, nei in graph[cur]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append(nei)
                    minimum_score = min(minimum_score, wei)
                
            return minimum_score
                    

        graph = defaultdict(list)
        answer = float('inf')

        for u, v, w in roads:
            graph[u].append([w, v])
            graph[v].append([w, u])
        
        return bfs(1)

- 결과

- 내 풀이 2 (Union-find)

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        parent = [i for i in range(n+1)]

        for u, v, _ in roads:
            if parent[u] != parent[v]:
                parent[find(u)] = find(v)

        return min(w for u, _, w in roads if find(u) == find(1))

- 결과