위상정렬(백준 알고리즘 14567번)
♣ 위상정렬의 정의위상정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 아래와 같은 비순환 방향 그래프(DAG: Directed Acyclic Graph) 에서 가능하다. 위의 DAG에서 노드들을 방향성에 거스르지 않는 순서대로 나열하면 아래와 같다. (위상정렬 결과) 예시1 예시2 사이클은 노드 사이에 선수관계를 알 수 없는 그래프를 의미한다. 사이클이 있는 방향 그래프에서는 어느 노드가 선순위에 있는지 알 수 없기 때문에 위상정렬이 불가능하다. ♣ 진입차수와 진출차수진입차수(Indegree)는 노드로 들어오는 간선의 수를 의미한다. 진출차수(Outdegree)는 노드에서 나가는 간선의 수를 의미한다. 위 그래프에서 노드 4를 예로 들면 진..
2024.11.20