[백준/Python] 2252번 - 줄 세우기

문제

백준 2252번 - 줄 세우기

해결 과정

• 위상 정렬
• 예시) 3명의 학생 중에서 키를 2번 비교
  1번이 3번보다 작고(1 -> 3), 2번이 3보다 작다 (2 -> 3)
  진입차수 indegree = [0, 0, 0, 2]
그래프 student = [[], [3], [3], []]
• 위상정렬의 과정은 다음과 같다.
  1. 진입차수가 0인 정점을 큐에 삽입
  • for문을 1부터 n까지 돌면서 진입차수가 0인 것을 큐에 삽입
  2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
  • 큐가 빌 때까지 반복문을 돌기
  • 현재 원소를 큐에서 빼고 result에 넣고
  • 현재 원소에 연결된 노드를 반복문 돌면서 연결된 간선에서 1 빼기
  3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입
  • 그 이후에 진입차수가 0이라면 큐에 삽입
  4. 이후 2~3의 과정을 반복

풀이

import sys
from collections import deque 
n,m = map(int,sys.stdin.readline().split())

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n+1)
student = [[] for _ in range(n+1)]

for _ in range(m):
  a, b = map(int,sys.stdin.readline().split())
  student[a].append(b)
  # 진입차수 1 증가
  indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
  result = []
  q = deque()
  for i in range(1, n+1):
    if indegree[i] == 0:
      q.append(i)
  while q:
    now = q.popleft()
    result.append(now)
    for i in student[now]:
      indegree[i] -= 1
      if indegree[i] == 0:
        q.append(i)
  for i in result:
    print(i, end=" ")
    
topology_sort()