[백준 알고리즘] 2252번: 줄 세우기 (Python)

Algorithm/백준

[백준 알고리즘] 2252번: 줄 세우기 (Python)

에릭 Kim 2023. 4. 5. 08:29

https://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

소스코드

풀이

방향 그래프의 모든 노드를 진입차수에 따라 순서대로 나열하는 위상 정렬을 활용한 문제입니다 !

사실 위상 정렬의 예시와도 같은 문제라 따로 풀이할 내용은 없는 거 같고, 위상 정렬을 아직 잘 모르신다면 다음 블로그를 참고하시는 것도 좋을 거 같아요 !

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

4https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=36 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미 예시) 선수

freedeveloper.tistory.com