Algorithm-문제집

백준 1766 : 문제링크

• 문제유형

  • 탐색
  • 힙
  • 위상정렬

• 설명

  • 위상정렬
    1. 진입 차수가 0인 정점을 큐에 삽입
    2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거
    3. 제거 이후 진입 차수가 0이 된 정점을 큐에 삽입
    4. 큐가 빌 때까지 2 ~ 3을 반복
  • 위상정렬 사용이유 : 2번 조건 - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.)
  • 힙 사용이유 : 3번 조건 - 가능하면 쉬운 문제부터 풀어야 한다

• 풀이

  import heapq
  
  n, m = map(int, input().split())
  array = [[] for i in range(n + 1)]
  indegree = [0] * (n + 1)
  
  heap = []
  result = []
  
  for _ in range(m):
      x, y = map(int, input().split())
      array[x].append(y)
      indegree[y] += 1
  
  for i in range(n+1):
      if indegree[i] == 0:
          heapq.heappush(heap, i)
      
  result = []
  
  while heap:
      data = heapq.heappop(heap)
      result.append(data)
      for y in array[data]:
          indegree[y] -= 1
          if indegree[y] == 0:
              heapq.heappuh(heap, y)
  
  for i in result:
      print(i, end = ' ')