반응형
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
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 4948번: 베르트랑 공준 (Python) (0) | 2023.04.07 |
|---|---|
| [백준 알고리즘] 1764번: 듣보잡 (Python) (0) | 2023.04.06 |
| [백준 알고리즘] 2294번: 동전 2 (Python) (0) | 2023.04.04 |
| [백준 알고리즘] 1010번: 다리 놓기 (Python) (0) | 2023.04.04 |
| [백준 알고리즘] 11722번: 가장 긴 감소하는 부분 수열 (Python) (0) | 2023.04.03 |