[BOJ C++] 2252 줄 세우기

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

2252번: 줄 세우기

 

 

문제 이해

N명의 학생들이 존재하고, 그들의 키를 순서대로 세워야 하는 문제였습니다. 주어지는 것은 두명의 키를 비교한 정보를 몇개 주는데, 이는 모든 학생을 비교해 본 것은 아닙니다. 주어진 정보만을 가지고 해당 조건을 만족하는 학생들의 순서를 정하는 문제였습니다.

 

 

입출력 조건

N은 최대 32000까지 가능하며 이후 M은 두 학생을 비교했다는 것을 뜻하며 최대 100,000까지 주어집니다.

시간제한은 2초였으며 모든 경우의 수를 따지기엔 32,000 * 100,000 -> 시간초과가 납니다.

 

 

풀이

모든 경우의 수를 탐색하기에는 시간초과가 날 것이 뻔했기에, 주어지는 학생들의 순서를 정점과 간선으로 생각하여 위상정렬을 이용하였습니다.

앞 순서의 학생에서 -> 뒷 순서의 학생으로 간선을 두고 in degree 의 갯수가 0인 것 부터 queue에 넣으며 순서를 정해주었습니다.

in degree가 0인 학생들을 먼저 처리해 주고, 처리된 정점에서 다른 정점으로 가는 간선이 있었다면 이후 정점들의 in degree를 하나씩 낮춰주고 다시 queue에 넣어주는 방식으로 문제를 해결하였습니다.

 

 

에러 및 느낀 점

위상정렬을 처음 문제에 적용해본 문제였습니다. 한번 실수가 있었던 점은, 굳이 해주지 않아도 되는 전체 정점 탐색을 굳이 한번 더 해줬다는 점이였습니다. 그래서 시간초과가 한번 떴었습니다..

 

 

전체코드

https://github.com/JuneYoungDo/Algorithm/blob/master/2252_%EC%A4%84%20%EC%84%B8%EC%9A%B0%EA%B8%B0.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.