백준 2252번 줄 세우기

< 백준 2252번 줄 세우기 - 마포 코딩박 >

사용한 알고리즘: 위상정렬


학생들의 부분적인 순서가 입력으로 주어졌을 때, 이를 만족하는 총 학생들의 배열을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~8, 15~22)
 'arr[i] : i 학생 뒤에 와야하는 학생들' , 'indegree[x] : x학생 앞에 서야하는 학생 수' 라고 설정하였습니다.
 각 입력을 받으며 arr 와 indegree를 최신화 해주었습니다.

(2) (코드 23~27)
 indegree가 0인, 즉 자신의 앞에 와야하는 학생이 없는 학생들을 골라 queue를 만들어 넣었습니다. 이 학생들은 맨 처음에 올 수 있는 학생들입니다.

(3) (코드 28~37)
 queue에 넣은 학생들을 하나씩 꺼내며, 그 순서가 곧 답이므로 답을 만듭니다.
 꺼낸 학생의 arr 를 둘러보며, 그 학생의 자식들의 indegree-- 를 해줍니다. 이때 indegree=0 이 되는 자식학생이 있으면 queue에 다시 넣어줍니다.