반응형
줄세우기
-
BOJ) 줄 세우기 (2252 번)알고리즘/백준 2021. 1. 2. 16:20
줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 오랜만에 포스팅을 하게 된 이유는 위상 정렬에 대한 정리를 하기 위해서이다. 위키에 따르면 위상 정렬(topological sorting)은 방향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 가장 대표적인 예로 대학의 선수과목(prerequisite) 구조를 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 ..