[알고리즘] 백준 2252 파이썬 - 줄 세우기 (위상정렬)

 

2252번: 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

문제풀이

from collections import deque
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
tmp=[0 for _ in range(n+1)]
q=deque()
ans=[]
for _ in range(m):
	#01
    a,b=map(int,input().split())
    graph[a].append(b)
    tmp[b]+=1
#02
for i in range(1,n+1):
    if tmp[i]==0:
        q.append(i)
while q:
	#03
    x=q.popleft()
    ans.append(x)
    for i in graph[x]:
        tmp[i]-=1
        if tmp[i]==0:
            q.append(i)
print(*ans)

- #01 : 입력받은 값 b를 graph의 a번째에 추가한다.

           tmp 값에 b에는 1을 추가하여 #02에서 바로 추가되지 않게 한다.

- #02 : tmp[i] 값이 0인 경우, 다시말해 #01에서 누군가의 뒤라고 지정되지 않은 

           값인 경우는 순서에 상관없이 줄을 세울 수 있기에 q에 추가해준다.

- #03 : q에 왼쪽 값을 추출하여 ans에 추가한다. 즉 줄을 세우는 과정이다.

           이후 graph[x] 값을 i에 넣어 tmp[i] 값을 1씩 감소시킨다.

           만약 tmp[i] 값이 0이 된 경우에는 #02와 같이 q에 추가해주고 

           while문을 통해 ans에 추가해준다.

           최종적으로 줄 지어진 ans를 한 줄에 출력한다.

 

(위상 정렬에 대한 자세한 설명은 아래 블로그를 참조)

위상 정렬(Topological sort) 개념 및 구현