[C++] 백준 2252 - 줄 세우기

🔐 백준 2252 - 줄 세우기

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

🔑 풀이

대표적인 위상 정렬 문제 중 하나이다. 여러 학생들 중 일부 학생들의 키의 비교가 주어질 때

전체 학생의 줄을 세우는 문제이며, 방향 그래프에서의 진입차수 개념을 활용하여 쉽게 해결 가능하다.

(물론 문제에서 주어지는 입력에서 사이클이 없어야 함.)

학생들 간의 키의 비교를 담을 adj 배열과 정점(학생)별 진입차수를 담을 in_degree 배열을 만들고,

입력을 모두 받은 후, 진입차수가 0인 학생들을 큐에 넣는다. (진입차수가 0이라는 것은 자신보다 큰 학생에

대한 입력이 주어지지 않았다는 뜻) 그 후, 큐의 값들을 하나씩 꺼내며, 인접한 정점들에 대해 진입차수 값을

1씩 감소시킨다.(위상 제거) 만약 진입차수가 0이 되는 정점(학생)이 발생한다면 큐에 넣어주며, 큐가 빌

때까지 반복한다.

🧩 코드