위상정렬에서 dfs가 종료되는 순서대로 찍고,
reverse를 하나요?
들어갈때 찍는거랑 순서가 다르지만,
선행노드는 잘나타내니까 상관없는거 아닌가요?
a -> c와 b -> c라는 간선이 있다고 합시다.
들어갈 때 출력을 하면 a c b 또는 b c a 둘 중 하나가 됩니다. 둘 중 어느 하나도 위상 정렬된 상태가 아니죠.
반면에 끝날 때 출력을 하면 c a b 또는 c b a 중 하나이고, 뒤집으면 b a c 또는 a b c로 위상 정렬이 잘 된 결과가 나옵니다.
감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
sotter1020 5년 전
위상정렬에서 dfs가 종료되는 순서대로 찍고,
reverse를 하나요?
들어갈때 찍는거랑 순서가 다르지만,
선행노드는 잘나타내니까 상관없는거 아닌가요?