줄 세우기[백준 2252] - python

import sys
input = sys.stdin.readline

def BOJ2252() :
  N, M = map(int, input().split())
  count_of_line = [0] * (N+1)
  graph = [[] for _ in range(N+1)]
  queue = []
  
  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 :
      queue.append(i)
  
  while queue :
    student = queue.pop(0)
    for i in graph[student] :
      count_of_line[i] -= 1
      if count_of_line[i] == 0 :
        queue.append(i) 
    print(student, end = ' ')

BOJ2252()

 

접근 방법 :

1. 위상정렬의 대표적인 문제이다. 

위상정렬을 언제 사용해야 하나면 선행되어야 하는 작업이 있을 때 이다.

만약 a보다 b가 먼저 선행되어야 한다면

1. a의 진입차수에 1을 추가해주고 b에서 a를 접근할 수 있다는 것을 기록해준다. 

2. 진입 차수가 0인것 부터 순차적으로 진행해주면 b전에 a를 실행할 수 밖에 없다. 이를 문제의 예시에서 설명해보자

이러한 예시가 있다고 치자. 

1. 일의 진행 가능 순서는 5 -> 4 -> 1 -> 3,  2 -> 3 순서이다.

2. 진입차수가 0인것은 5와 2이다.

3. 5와 2를 탐색 queue에 넣어주자

4. 5와 2는 서로 연관이 없으므로 어느 일이 먼저 수행되든 상관없다. 5와 2를 수행하면 이전에 5와 2를 참조하던 노드에서는 진입차수를 하나씩 제거해주어야 한다.

5. 이제 진입차수가 0인 4를 수행할 수 있고 이렇게 하나씩 수행하다보면 

4 -> 1 -> 3 순서대로 출력해 낼 수 있다.

 

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

2252번: 줄 세우기