[Python 3] 백준 2252-줄 세우기

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

2252번: 줄 세우기

위상 정렬

위상 정렬은 DAG(Directed Acylic Graph, 사이클이 없는 유향그래프)에서만 성립한다. 정점들을 방향성에 맞게(화살표의 역순이 없도록)정렬한다. 다른 정렬과 다르게 위상정렬은 답이 한 가지가 아닐 수도 있다. 방향성만 만족한다면 어떠한 형태가 나와도 가능하다.

 

그래프에서 진입 차수(특정 정점을 가리키는 간선의 수)가 0인 경우는 이 정점을 선택하기 전에 무조건 골라야 할 정점이 더 이상 없다는 것을 의미한다. 즉 선택해도 된다는 뜻이다. 결과적으로 정점을 전부 선택할 때까지 진입 차수가 0인 정점을 선택해 정렬하고 그 정점과 거기서 출발하는 간선들을 전부 제거하는 것을 반복하면 위상 정렬을 할 수 있다.

 

매 번 반복문이 돌아갈 때마다 정점 한 개가 정렬되므로, 정점의 수만큼 반복하면 된다.

import sys
from collections import deque

N, M=map(int, sys.stdin.readline().split())
graph={}
pointing=[0 for i in range(N+1)]
topsort=[]
for i in range(1, N+1):
  graph[i]=[]
for i in range(M):
  A, B=map(int, sys.stdin.readline().split())
  graph[A].append(B)
  pointing[B]+=1
dq=deque()
for i in range(1, N+1):
  if pointing[i]==0:
     dq.append(i)
for i in range(N):
  top=dq.popleft()
  topsort.append(top)
  for j in graph[top]:
    pointing[j]-=1
    if pointing[j]==0:
      dq.append(j)
print(' '.join(map(str, topsort)))