[백준 2252 줄 세우기 문제] PYTHON

 

이 문제는 위상 정렬을 사용해서 푸는 문제다.

위상 정렬이란 사이클이 없고 방향만 존재하는 vertex를 나열하는 것이다.

이 문제에선 키를 비교한 리스트에서 자신을 참조한 (자신보다 앞에선) vertex가 0인 것을 큐에 넣는다.

- 여기서 무조건 맨 뒤에 있는 vertex는 0이므로 무조건 값이 있음 -

그 후 queue를 while문을 통해 돌리며 자신을 참조한 value들의 참조값을 -1 하며

queue 내의 index를 remove하고 다시 참조값이 0인 vertex를 append하며 반복을 하면 된다.

 

코드로 구현하면 아래와 같다.

N, M = map(int, input().split())
indegree = [0 for i in range(N+1)]
Tlist = [[] for i in range(N+1)]
queue = []
answer = []
for _ in range(M):
    a, b = map(int, input().split())
    Tlist[a].append(b)
    indegree[b] += 1

for j in range(1, N+1):
    if indegree[j] == 0:
        queue.append(j)

while(queue):
    for i in queue:
        answer.append(i)
        queue.remove(i)
        for t in Tlist[i]:
            indegree[t] -= 1
            if(indegree[t] == 0):
                queue.append(t)

for ans in answer:
    print(ans, end=" ")