2252번1 [백준] 2252 줄세우기 문제 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 분석 : 이 문제는 종만북 DFS BFS 부분의 대표적인 예제 중 위상 정렬에 관한 문제였다. 위상 정렬이란 의존성이 있는 작업이 주어질 때 이를 어떤 순서로 수행해야 하는지 계산한다. 이때 의존 관계를 DAG(사이클 없는 그래프) 로 표현한다. 사이클이 없다는 뜻은 즉 한 방향에서 한 방향으로 흘러가는 꼴의 그래프를 말한다. 그렇기 때문에 기존 DFS BFS 는 트리 .. 2021. 2. 14. 이전 1 다음