오늘은 DFS를 마치고 위상정렬에 대해 공부하기 시작했다. 위상 정렬 위상 정렬이란? 방향이 있는 그래프에서 방향을 거스르지 않고 모든 정점을 잇는 경로를 선형순서로 나열하는 것 이때 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 이때 든 생각은, 알고리즘 문제에서 일단 사이클이 있는지를 판단하고 사이클이 있다면 위상 정렬을 하도록 하는 문제가 있을 거라 생각했다. 사이클이 있는지 판단하는 함수는 Kruskal에서의 노드의 부모를 고정하여 판단하는 방식이 사용될 것 같다. [정방향] 위상 정렬의 동작 예시(경로를 나열하기 위한 진행 순서)는 다음과 같다. 1. 진입차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐에서 POP을 하고 POP한 노드에서 나가는 간선을 제거한다. 3. 제거한 후 진입차..
