2252 줄 세우기

위상정렬의 대표적인 문제

[참고] https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[참고] https://blog.naver.com/ndb796/221236874984

위상정렬은 먼저 DAG(Directed Acyclic Graph)을 기반으로 하는 알고리즘이다. DAG는 방향 그래프와 비사이클 그래프를 모두 만족하는 그래프다. 따라서 순서가 정해진 그래프로, 순서를 지키며 정렬하는 알고리즘이 위상정렬이다.

탐색을 하면서 가장 중요한 요소는 자신 전에 존재하는 노드들(차수) 그리고 자신 다음의 노드 총 2가지다.

그래서 차수가 0인 것을 먼저 큐에 넣고 탐색을 진행한다. 그리고 그와 연결된 차수를 하나씩 지워나가면서 차수가 0인 것을 계속 큐에 놓고 큐가 비워질 때까지 반복하는 구조다.

문제: https://www.acmicpc.net/problem/2252

깃허브코드: https://github.com/surinoel/boj/blob/master/2252.cpp