위상정렬
-
[백준] Java - 줄 세우기메모/알고리즘 2022. 6. 1. 23:52
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 백준의 위상정렬 문제 줄 세우기의 자바 풀이다. 위와 같이 순서가 정해져 있고 사이클이 없는 그래프를 정렬하는 알고리즘이 위상정렬이다. "진입 차수"와 "인접 리스트"를 통해서 문제를 해결할 수 있었다. 위의 그림에서 6을 보면 4와 5로부터 진입하는 것을 볼 수 있다. 2개의 노드가 6으로 진입하므로 진입 차수는 2이다. 반대로 1이나 2는 진입차수가 0이다. 인접리스트를 통해 연결된 다음 노드를 저장하고 진입차수가 ..