문제집 [백준 1766] - python

import heapq
import sys
input = sys.stdin.readline

# 번호가 작은 문제를 먼저 풀어야 하므로 heapq를 사용하자

def BOJ1766() :
  N, M = map(int, input().split())
  count_of_line = [0] * (N+1)
  graph = [[] for _ in range(N+1)]
  heap = []
  result = []
  
  for _ in range(M) :
    a, b = map(int, input().split())
    count_of_line[b] += 1
    graph[a].append(b)
    
  for i in range(1, N+1) :
    if count_of_line[i] == 0 :
      heapq.heappush(heap, i)

  while heap :
    curr = heapq.heappop(heap)
    result.append(curr)
    for i in graph[curr] :
      count_of_line[i] -= 1
      if count_of_line[i] == 0 :
        heapq.heappush(heap, i)

  print(*result)
BOJ1766()

 

접근방법 :

1. 위상정렬을 적용해야하는 문제이다. 근데 이제 조건이 하나 있다. 

2. 가능하면 쉬운 문제부터 풀어야 한다. 번호가 작은 숫자가 쉬운 문제이다. 위상정렬을 적용할때 queue를 적용해야 하는데 이 queue에서 매번 정렬을 해주어야 한다.

3. 값이 들어갈때마다 정렬이 되는 큐는 우선순위 큐이다!!! 이 문제는 결국 위상정렬 문제인데 이제 우선순위 큐를 곁들인 문제라 할 수 있다.

4. 우선순위 큐가 빌때까지 탐색을 진행해주면 된다!!

 

 

장애물 이였던 것 : 

1. 우선순위 큐를 적용할 때는 문제의 조건에서 동등한 단계에 있는 친구들 사이에 순위가 정해져 있으면 우선순위 큐를 적용하자

선행되어야 하는 작업이 있는 경우는 위상정렬이다.

탐색에서 규칙적으로 값이 변경되는 것은 배열 + dfs or bfs

탐색에서 불규칙적으로 값이 변경되는 것은 dictionary + dfs or bfs

 

 

 

https://www.acmicpc.net/problem/1766

1766번: 문제집