2252
-
백준(BOJ) 2252번 줄 세우기알고리즘 풀이/백준(Boj) 2019. 7. 25. 02:27
문제 : https://www.acmicpc.net/problem/2252 문제N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 나의풀이 : DFS를 이용한 위상 정렬로 문제를 풀어 보았다. 1~N까지 dfs가 종료하는 순서를 기록한 뒤 이 순서를 뒤집는다. 그래프에 사이클이 없다면 이 순서는 그래프의 위상 정렬 결과가될 것. 코드 ( C ++ ) #include #include #include #include u..