[BOJ] 2252 줄 세우기 Python

 

위상정렬 (topological sort)에 대한 내용이 나왔다.

 

복습으로서는 굉장히 좋을 것 같다 !

from collections import deque
N,M = map(int,input().split())

graph = [[] for _ in range (0,N+1)]
ind = [0 for _ in range (0,N+1)]
for _ in range (0,M):
    a,b = map(int,input().split())
    graph[a].append(b)
    ind[b] += 1

deq = deque()
for i in range (0,N+1): #진입차수가 0인 친구들 먼저 추가 (끝에 있는 친구들부터)
    if ind[i] == 0:
        deq.appendleft(i)

ans = []
while deq:
    x = deq.popleft()
    if x == 0:
        break
    ans.append(x)
    for j in range (0,len(graph[x])):
        ind[graph[x][j]] -= 1
        if ind[graph[x][j]] == 0:
            deq.appendleft(graph[x][j])
answer = " ".join(str(s) for s in ans)
print(answer)

 

역시 주요한 아이디어는, Indegree가 0인 노드를 추가하면서 (이 친구가 시작점이 되기 때문)

 

그 노드에서 이어진 Node들의 indegree를 1씩 줄여가며 찾아내가는 방법이 되겠다.