위상정렬 (Topological Sort)
- 선후 관계가 정의된 그래프 구조에서 정렬하기 위해 사용
- 그래프가 순환 구조 가지면 사용 불가
동작
- 진입 차수 테이블 생성 및 진입 차수 계산
- 진입 차수가 0인 노드 큐에 넣기 (순서 상관 X)
- 큐에서 노드 꺼내 연결된 노드들 진입 차수 감소 ( -1 해준다), 진입 차수가 0이 되면 큐에 넣기
- 큐가 비어버릴 때 까지 3번 반복하며 꺼낸 노드들 줄세우기 (이게 위상 정렬 결과값)
백준 문제 : 2252번: 줄 세우기 (acmicpc.net)
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
반응형
'미가공 필기(알고리즘)' 카테고리의 다른 글
| 유니온 파인드( Union Find ) (0) | 2022.02.18 |
|---|---|
| 220117 이분탐색 : UpperBound vs LowerBound (0) | 2022.01.17 |
| 210713 NP vs P (0) | 2021.07.13 |
| 210712 Matrix Multiplication , 플로이드-와샬(Floyd-Warshall 알고리즘) (0) | 2021.07.13 |
| 210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) (0) | 2021.07.13 |
댓글