본문 바로가기

위상정렬

[Python] 위상 정렬 - 재귀 없는 DFS
알고리즘 2022. 5. 27. [Python] 위상 정렬 - 재귀 없는 DFS 재귀를 사용하지 않는 위상 정렬 코드가 없어서 스택오버플로의 도움을 받아 직접 구현해보았다. 재귀를 사용하지 않기 때문에 단순히 방문 여부 뿐만 아니라 현재 탐색 중인 길인지를 표시하면서 가야 한다. 쉽게 설명하면 기존의 스택 버전 DFS는 미로 같은데서 지나간 길에 빵쪼가리를 떨어뜨려 방문 여부만 확인하고 가는 것이라면 위상 정렬에서는 나뭇가지로 길을 그리면서 가는 것이다. 이렇게 쭉 가다가 안쪽까지 다다르게 되었을 때 그려진 길만 위상정렬한 결과에 역순으로 넣게 된다. 예를 들어 다음과 같은 DAG가 있다면 기존 DFS대로 꺼내서 방문 여부만 확인해 순차대로 넣게 된다면 1,3,4,2 로 쌓이게 된다. 스택에 연결된 정점을 모두 넣고 뒤에서부터 하나씩 꺼내기 때문이다. 완성된 코드 # 정점의 갯수, ..

티스토리툴바