Leetcode 3620. Network Recovery Pathways

문제

You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi.

Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online.

A path from 0 to n − 1 is valid if:

All intermediate nodes on the path are online.
The total recovery cost of all edges on the path does not exceed k.
For each valid path, define its score as the minimum edge‑cost along that path.

Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.

0부터 n - 1까지 번호가 매겨진 n개의 노드로 이루어진 방향 비순환 그래프(DAG)가 주어집니다.
그래프는 길이가 m인 2차원 배열 edges로 표현되며, edges[i] = [ui, vi, costi]는 노드 ui에서 노드 vi로 가는 단방향 통신이 있고,
복구 비용이 costi임을 의미합니다.

일부 노드는 오프라인 상태일 수 있습니다. boolean 배열 online이 주어지며, online[i] = true이면 노드 i가 온라인 상태임을 의미합니다.
노드 0과 노드 n - 1은 항상 온라인 상태입니다.

0에서 n - 1까지의 경로가 유효하려면 다음 조건을 만족해야 합니다.

모든 중간 노드는 온라인 상태여야 합니다.
경로에 포함된 모든 간선의 총 복구 비용이 k를 초과하지 않아야 합니다.
각 유효한 경로에 대해, 그 경로의 점수는 해당 경로에 포함된 간선 비용 중 최솟값으로 정의합니다.

모든 유효한 경로 중에서 가능한 최대 경로 점수, 즉 최소 간선 비용을 최대화한 값을 반환하세요.
유효한 경로가 존재하지 않으면 -1을 반환하세요.

---

예시

Input: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10

0 -> 1 -> 3 으로 가는 경우 총 비용이 15라 k인 10보다 커서 불가능
0 -> 2 -> 3 으로 가는 경우 총 비용이 7이기에 가능함, 점수는 3

가능한 경우가 1개 뿐이라 그중 최대 점수인 3이 output이 된다.

---

제한

• $n == online.length$
• $2 <= n <= 5 * 10^4$
• $0 <= m == edges.length <= min(10^5, n * (n - 1) / 2)$
• $edges[i] = [ui, vi, costi]$
• $0 <= u_i, v_i < n$
• $u_i \ne v_i$
• $0 <= cost_i <= 10^9$
• $0 <= k <= 5 * 10^13$
• online 배열의 모든 값은 True/False, 양 끝단의 값은 무조건 True
• 주어진 그래프에 사이클은 없다.

---

풀이

online 처리하기

• 일단 먼저 online에서 false인 노드들을 제외한다

그래프 만들기

• 가중치가 k보다 큰 엣지는 포함해도 쓸수 없기 때문에 제외한다.
• 위에서 추려낸 offline인것도 제외한다.
• 여기서 가중치의 최소, 최대 값을 추적한다.

풀이

• 사실 해당 문제의 풀이는 이진 탐색으로 가능하다.

어떻게???

값 x에 대해, x보다 길이가 크거나 같은 가중치를 가진 엣지만으로 전체 합이 k 이하인 (0 -> N - 1) 경로를 만들수 있는지 확인하는 함수

• 를 만들어서 그래프를 만들때 구한 최소, 최댓값을 통해 이진탐색한다.

from collections import defaultdict
from heapq import heappop, heappush
from typing import List


class Solution:
    def findMaxPathScore(
        self, edges: List[List[int]], online: List[bool], k: int
    ) -> int:
        graph = defaultdict(list)

        minima = float("inf")
        maxima = -float("inf")

        for s, e, c in edges:
            if c > k:
                continue

            if not online[s] or not online[e]:
                continue

            graph[s].append((e, c))
            minima = min(minima, c)
            maxima = max(maxima, c)

        if maxima == -float("inf"):
            return -1

        n = len(online)

        def check(least: int) -> bool:
            heap = [(0, 0)]
            dist = defaultdict(lambda: float("inf"))
            dist[0] = 0

            while heap:
                cost, node = heappop(heap)

                if cost > dist[node]:
                    continue

                if node == n - 1:
                    return True

                for dest, weight in graph[node]:
                    if weight < least:
                        continue

                    new_cost = cost + weight

                    if new_cost > k:
                        continue

                    if new_cost >= dist[dest]:
                        continue

                    dist[dest] = new_cost
                    heappush(heap, (new_cost, dest))

            return False

        ans = -1

        left = minima
        right = maxima

        while left <= right:
            mid = (left + right) // 2

            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans

• 이진탐색이라는 아이디어를 꺼내기가 어려웠지, 구현 자체는 생각보다 쉽다.