백준 [2252] 줄 세우기 (파이썬 풀이)

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

2252번: 줄 세우기

이 문제는 두 학생의 키 순서를 입력값으로 받기 때문에 위상 정렬 알고리즘을 사용해서 풀이해야한다.

 

위상 정렬이란?

순서가 정해진 작업을 순차적으로 진행할 때 그 순서를 구하는 알고리즘이다.

작업에는 이 작업을 하기 전 수행하는 선행 작업을 위배 하지 않으면서 순서를 나열해야 한다.

 

위상정렬의 조건

DAG(Directed Acyclic Graph) 이여야한다.

즉, 그래프에 서클이 존재 하지 않아야 위상정렬을 적용할 수있다.

 

내가 한 풀이

from collections import deque
n,m=map(int,input().split(" "))
graph=[[] for i in range(n+1)]
ingraph=[0]*(n+1)

for _ in range(m):
    x,y=map(int,input().split(" "))
    graph[x].append(y) #x 보다 키가 작은 y를 graph[x]에 저장한다.
    ingraph[y]+=1

q=deque()
answer=[]

for i in range(1,n+1):
    if ingraph[i]==0:
        q.append(i)

while q:
    a=q.popleft()
    answer.append(a)
    for inj in graph[a]:
        ingraph[inj]-=1
        if ingraph[inj]==0:
            q.append(inj)

print(*answer)