[Python] 위상 정렬 - 재귀 없는 DFS

재귀를 사용하지 않는 위상 정렬 코드가 없어서 스택오버플로의 도움을 받아 직접 구현해보았다.

재귀를 사용하지 않기 때문에 단순히 방문 여부 뿐만 아니라 현재 탐색 중인 길인지를 표시하면서 가야 한다.

쉽게 설명하면

기존의 스택 버전 DFS는 미로 같은데서 지나간 길에 빵쪼가리를 떨어뜨려 방문 여부만 확인하고 가는 것이라면

위상 정렬에서는 나뭇가지로 길을 그리면서 가는 것이다.

이렇게 쭉 가다가 안쪽까지 다다르게 되었을 때 그려진 길만 위상정렬한 결과에 역순으로 넣게 된다.

예를 들어 다음과 같은 DAG가 있다면

기존 DFS대로 꺼내서 방문 여부만 확인해 순차대로 넣게 된다면 1,3,4,2 로 쌓이게 된다.

스택에 연결된 정점을 모두 넣고 뒤에서부터 하나씩 꺼내기 때문이다.

단순히 DFS 스택버전을 사용한 경우 전위순회 순서로 쌓인다.

 

완성된 코드

# 정점의 갯수, 간선의 갯수
vertexes,edges=map(int,input().split())
# 인접리스트
adj_list=[[] for _ in range(vertexes+1)]

# 연결리스트 작성
for _ in range(edges):
    i,j=map(int,input().split())
    adj_list[i].append(j)

topology_sort=[] # 위상정렬 결과를 저장하는 스택
nvisit=[1]*(vertexes+1) #방문 확인용.방문은 0 미방문은 1

# 위상정렬 1 사이클 함수
def Topology_Sort_DFS(x):
    stack=[] #깊이 우선 탐색용 스택
    stack.append((0,x)) # (지나온 길,시작점) 넣기
    while stack:
        isRoute,curr=stack.pop() #스택에 저장된 최근 길
        if isRoute:topology_sort.append(curr) # 지나온 길이면 위상정렬결과에 넣는다.
        if nvisit[curr]: # t에 방문한 적이 없으면
            nvisit[curr]=0 # t에 방문하고
            stack.append((1,curr)) # 현재 지나온 길임을 표시하고 다시 넣는다.
            #t와 연결된 곳 중 방문하지 않은 곳만 아직 지나온 길이 아님을 표시하고 모두 스택에 넣는다.
            for i in adj_list[curr]:
                if nvisit[i]:stack.append((0,i))

# 모든 점에 대해서 위상정렬 사이클을 돌림
for i in range(1,vertexes+1):
    if nvisit[i]:Topology_Sort_DFS(i)

print(topology_sort[::-1])