2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [문제 설명] [문제 풀이] 이 문제를 풀기전에 위상정렬 알고리즘에 대해 알고 있으면 쉽게 풀 수 있다. 위상정렬 알고리즘에 대해 잘 모른다면 아래 포스트를 읽고오면 푸는데 도움이 될 것이다. [Algorithm] - Topology Sort(위상정렬) 위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 ..

위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 그래프를 방향을 거스르지 않도록 나열하는 것이다. 아래 그림을 참고하자. 위상정렬을 가장 잘 설명해줄수 있는 예로 대학교의 선수과목 구조를 예로 들 수 있다. 만약, 특정 과목을 듣기위해 필요한 선수 과목이 있다면, 그 선수과목부터 수강해야 한다. 이때 위상정렬을 사용하면 올바른 강의 순서를 찾아 낼 수 있다. 그래프의 구조에 따라 여러개의 정렬이 나타날 수도 있다. 위상정렬을 사용하기 위해선 시작노드를 특정하기 위해 DAG(Directed Acyclic Graph)여야만 한다. DAG는 사이클이 존재하지 않고, 하나의 방향만을 가지는 그..