LeetCode 1376. Time Needed to Inform All Employees

Graph Theory 문제 5번
https://leetcode.com/problems/time-needed-to-inform-all-employees/

나의 풀이(240ms, 79.66%)

BFS

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list) # direct_manager:[employee1, employee2, ...]
        q = collections.deque([headID])
        time_to_reach = {headID: 0}

        for employee, direct_manager in enumerate(manager):
            if employee != headID:
                graph[direct_manager].append(employee)
        
        while q:
            direct_manager = q.popleft()
            new_time = time_to_reach[direct_manager] + informTime[direct_manager]
            for employee in graph[direct_manager]:
                time_to_reach[employee] = new_time
                q.append(employee)
                
        return max(time_to_reach.values())

다른 풀이1(279ms, 57.35%)

BFS

• 마찬가지로 BFS인데 time_to_reach가 굳이 필요 없구나.

class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        graph = defaultdict(list)
        
        for emp, m in enumerate(manager):
            if m != -1:
                graph[m].append(emp)

        q = deque([(headID, 0)])  # (node, time)
        max_time = 0

        while q:
            node, time = q.popleft()
            max_time = max(max_time, time)
            for nei in graph[node]:
                q.append((nei, time + informTime[node]))

        return max_time

다른 풀이2(350ms, 23.66%)

DFS, recursive

class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        from collections import defaultdict

        graph = defaultdict(list)
        for i, m in enumerate(manager):
            if m != -1:
                graph[m].append(i)

        def dfs(node):
            if not graph[node]:  # leaf node
                return 0
            max_time = 0
            for emp in graph[node]:
                max_time = max(max_time, dfs(emp))
            return informTime[node] + max_time

        return dfs(headID)

다른 풀이3(212ms, 89.07%)

DFS, memoization, top-down

class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        memo = {}

        def dfs(emp):
            if emp == headID:
                return 0
            if emp in memo:
                return memo[emp]
            time = informTime[manager[emp]] + dfs(manager[emp])
            memo[emp] = time
            return time

        return max(dfs(i) for i in range(n))

다른 풀이4(391ms, 13.53%)

DFS, bottom-up

class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        from collections import defaultdict

        graph = defaultdict(list)
        for emp, m in enumerate(manager):
            if m != -1:
                graph[m].append(emp)

        dp = [0] * n

        def dfs(emp):
            if not graph[emp]:
                return 0
            if dp[emp] > 0:
                return dp[emp]
            dp[emp] = informTime[emp] + max(dfs(e) for e in graph[emp])
            return dp[emp]

        return dfs(headID)

다른 풀이5(100ms, 98.12%)

DFS, top-down, path compression

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def find(i):
            if manager[i] > -1:
                informTime[i] += find(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(map(find, range(n)))