2023.02.11 Today's Challenge

fabichoi 2023. 2. 11. 23:45

https://leetcode.com/problems/shortest-path-with-alternating-colors/

Shortest Path with Alternating Colors - LeetCode

Shortest Path with Alternating Colors - You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges. You are given

leetcode.com

BFS로 풀면 되는 문제!

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        graph = [[[], []] for i in range(n)]
        for s, e in redEdges:
            graph[s][0].append(e)
        for s, e in blueEdges:
            graph[s][1].append(e)

        dis = [[0, 0]] + [[float('inf'), float('inf')] for i in range(n-1)]
        qu = [[0, 0], [0, 1]]

        for node, color in qu:
            for nei in graph[node][color]:
                if dis[nei][color] == float('inf'):
                    dis[nei][color] = dis[node][1-color] + 1
                    qu.append([nei, 1-color])
        return [d if d < float('inf') else -1 for d in map(min, dis)]