LeetCode 솔루션 분류
[2/11] 1129. 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 two arrays redEdges and blueEdges where:
redEdges[i] = [ai, bi]indicates that there is a directed red edge from nodeaito nodebiin the graph, andblueEdges[j] = [uj, vj]indicates that there is a directed blue edge from nodeujto nodevjin the graph.
Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.
Example 1:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]
Example 2:
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]] Output: [0,1,-1]
Constraints:
1 <= n <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= ai, bi, uj, vj < n
Accepted
58K
Submissions
129.9K
태그
#Bloomberg
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
from collections import defaultdict, deque
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
blue = defaultdict(list)
red = defaultdict(list)
for v1, v2 in redEdges:
red[v1].append(v2)
for v1, v2 in blueEdges:
blue[v1].append(v2)
res = [-1]*n
res[0] = 0
queue = deque([(0,0,1), (0,0,-1)])
visited = set()
while queue:
node, dis, color = queue.popleft()
if res[node] == -1: res[node] = dis
visited.add((node,color))
if color == 1:
for nxt in red[node]:
if (nxt, color*-1) not in visited: queue.append((nxt,dis+1, color*-1))
else:
for nxt in blue[node]:
if (nxt, color*-1) not in visited: queue.append((nxt,dis+1, color*-1))
return res
