[Python] 백준 2252 - 줄 세우기

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

2252번: 줄 세우기

Topology(위상정렬) 알고리즘 문제다.

 

위상정렬의 알고리즘은 다음과 같이 진행된다.

1. indegree(진입차수)가 0인 노드를 찾고 큐에 넣는다.

2. 큐에서 노드를 꺼내고 해당 노드와 연결되는 모든 노드를 탐색한다.
3. 탐색되는 노드들의 indgree 값을 1씩 감소시킨다.
4. 탐색된 노드들 중 indgree 값이 0인 노드를 큐에 넣는다.

5. 2~4번을 큐가 빌 때까지 반복한다.

 

위상정렬 뭔가 이름이 어렵게 생겼는데 배우고나니 할만한 것 같다.

위상정렬이 처음이라면 해당 문제가 가장 적절해보인다.

from collections import deque

n,m = map(int,input().split())

student = [[] for i in range(n+1)]
indeg = [0]*(n+1)

for _ in range(m):
    a,b = map(int,input().split())
    student[a].append(b)
    indeg[b]+=1

result = []
q = deque()

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

while q:
    x = q.popleft()
    result.append(x)
    
    for i in student[x]:
        indeg[i]-=1
        if indeg[i] == 0:
            q.append(i)

for i in result:
    print(i,end=' ')