BOJ/Topological Sort
-
[Python 3] 백준 2252-줄 세우기BOJ/Topological Sort 2020. 3. 4. 00:04
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상 정렬 위상 정렬은 DAG(Directed Acylic Graph, 사이클이 없는 유향그래프)에서만 성립한다. 정점들을 방향성에 맞게(화살표의 역순이 없도록)정렬한다. 다른 정렬과 다르게 위상정렬은 답이 한 가지가 아닐 수도 있다. 방향성만 만족한다면 어떠한 형태가 나와도 가능하다. 그래프에서 진입 차수(특정 정점을 가리키..