[Leetcode] - 1136

  • 각 노드로 들어오는 엣지의 개수가 0일때 해당 노드를 방문할 수 있음
  • 각 노드로 들어오는 엣지 개수 카운터를 만들어 관리해야함
  1. que에 현재 들을 수 있는 강의 넣기
  2. 방문하면서 연결되어있는 노드의 in_node counter 감소시키기
  3. 해당 연결노드를 다음번에 방문할 수 있으면 (counter == 0) next_que 에 넣기
  4. 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
            

좋은 웹페이지 즐겨찾기