2023.11.12 Today's Challenge

fabichoi 2023. 11. 12. 23:45

https://leetcode.com/problems/bus-routes/

Bus Routes - LeetCode

Can you solve this real interview question? Bus Routes - You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. * For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in

leetcode.com

이번에도 BFS로 푸는 문제

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        
        max_stop = max(max(route) for route in routes)
        if max_stop < target:
            return -1

        n = len(routes)
        min_buses_to_reach = [float('inf')] * (max_stop + 1)
        min_buses_to_reach[source] = 0

        flag = True
        while flag:
            flag = False
            for route in routes:
                m = float('inf')
                for stop in route:
                    m = min(m, min_buses_to_reach[stop])
                m += 1
                for stop in route:
                    if min_buses_to_reach[stop] > m:
                        min_buses_to_reach[stop] = m
                        flag = True
        
        return min_buses_to_reach[target] if min_buses_to_reach[target] < float('inf') else -1