[Leetcode] - 1136
6595 단어 BFSDFSTopological SortBFS
- 각 노드로 들어오는 엣지의 개수가 0일때 해당 노드를 방문할 수 있음
- 각 노드로 들어오는 엣지 개수 카운터를 만들어 관리해야함
- que에 현재 들을 수 있는 강의 넣기
- 방문하면서 연결되어있는 노드의 in_node counter 감소시키기
- 해당 연결노드를 다음번에 방문할 수 있으면 (counter == 0) next_que 에 넣기
- next_que 에 대해 같은 동작 수행
class Solution:
def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
# graph build
# in-node counter
graph = {i:[] for i in range(1, n+1)}
in_node = {i:0 for i in range(1, n+1)}
for r in relations:
graph[r[0]].append(r[1])
in_node[r[1]] += 1
max_d = -1
nstudied = 0
que = [(k, 1) for k, v in in_node.items() if v == 0]
while que:
next_que = []
for vd in que:
v, d = vd
if d > max_d:
max_d = d
nstudied += 1
for next_v in graph[v]:
in_node[next_v] -= 1
if in_node[next_v] == 0:
next_que.append((next_v, d+1))
que = next_que
if nstudied == n:
return max_d
return -1
Author And Source
이 문제에 관하여([Leetcode] - 1136), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jisngprk/Leetcode-1136저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)