2252
-
Python 백준 2252 - 줄 세우기(위상 정렬)프로그래머스문제정리 & Python잡다한것 2021. 6. 4. 00:55
위상 정렬(Topological Sorting) 조건 : Cycle 이 없는, 유향 그래프에 대해서 정렬을 수행한다. (DAG) 문제 풀이 순서 1. 그래프를 구현한다. -> list형태로 구현, 무방향 그래프(양방향 그래프)가 아닌 유방향 그래프로 나타낸다. 2. Indgree(노드에 들어가는 진출 차수)를 그래프를 표현할때 같이 배열로 설정해 놓는다. 3. indgree 가 0 인 것을 queue에 넣는다. 그리고 탐색을 시작한다.(어짜피 indgree가 같은 것은 순서에는 상관이 없을 것이다.) 4. queue에서 하나를 빼고 해당 값을 결과 List에 넣는다. 본인과 연결된 Node의 indgree 값을 하나 빼준다. -> edge를 지우는 것을 의미한다. 5. indgree가 0이 되는 Node..