2022.02.17 [백준] (python 파이썬) 줄 세우기

 

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

2252번: 줄 세우기

---

풀이

다음 문제는 위상 정렬을 사용하면 쉽게 해결할 수 있다.

이유는 각 비교 학생들을 앞에 서야 하는 학생 쪽으로 화살표를 그리면 진입 차수와 진출 차수를 알 수 있다. 

그래서 진입 차수가 0이면 앞에 서야하는 학생이 없는 뜻이기 때문에 deque를 이용하여 진입차수가 0인 학생들을 result에 저장 후 출력했다. 이 때 각 학생의 진입 차수 즉 앞에 서야하는 학생의 수를 check에 카운트했다.

from collections import deque
 
n,m=map(int,input().split())
check=[0]*(n+1)
graph=[[] for _ in range(n+1)]
 
for _ in range(m):
    x,y=map(int, input().split())
    graph[x].append(y)
    check[y]+=1
 
result=[]
deq=deque()
 
for i in range(1,n+1):
    if check[i]==0:
        deq.append(i)
 
while deq:
    a=deq.popleft()
    result.append(a)
    for i in graph[a]:
        check[i]-=1
        if check[i]==0:
            deq.append(i)
for i in result:
    print(i,end=" ")