반응형 22521 파이썬(Python) 위상정렬 - 개념과 예제 (백준 2252) 위상 정렬 위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다. 사이클이 있다면 노드 순서가 정의되지 않고, 위상정렬은 항상 유일한 값으로 정렬되진 않습니다. 그래프가 있을때 인접리스트와 진입차수 리스트를 만들어야 합니다. 진입차수리스트는 자신을 가리치는 노드의 갯수를 의미하고, 인접리스트를 이용해서 만들수 있습니다. adjacent (인접리스트) 1 -> 2 3 2 -> 4 5 3 -> 4 4 -> 5 5 진입 자수 리스트 (in-degree) 각 노드마다 자신을 가리키는 노드의 갯수를 기록 하면 됩니다. 예를 들어 4는 2,3이 가리키고 있으므로 2입니다. 노드 1 2 3 4 5 차수 0 1 1 2 2 진입 차수 리스트에서 차수가 0인 것을 우선 선택하고 위상 정렬 리스트 첫번째.. 2022. 10. 15. 이전 1 다음
