공개 기출자동 검사 완료2025년 지방직 기출 · 컴퓨터일반 · 자료구조·알고리즘 · 20번

위상 정렬(topological sort)이 가능한 그래프만을 모두 고르면?

ITPASSLAB 재구성 문제 자료

1
ㄱ, ㄴ
오답 이유ㄴ에는 방향이 없는 간선이 포함되어 위상 정렬의 대상인 방향 비순환 그래프가 아니므로 오답입니다.
2
ㄱ, ㄹ
정답 근거ㄱ과 ㄹ은 방향 그래프이며 사이클이 없어 선행 관계를 만족하는 위상 정렬이 가능합니다.
3
ㄴ, ㄷ
오답 이유ㄴ은 방향 그래프가 아니고 ㄷ에는 방향 사이클이 존재하므로 둘 다 위상 정렬할 수 없습니다.
4
ㄷ, ㄹ
오답 이유ㄷ은 방향 사이클 때문에 위상 정렬이 불가능하므로 ㄹ과 함께 고른 조합은 오답입니다.

정답·상세해설

정답 2번

위상 정렬은 방향 그래프에 순환이 없을 때, 즉 DAG일 때만 가능합니다. 그림의 ㄱ과 ㄹ은 모든 간선 방향을 따라가도 시작 정점으로 돌아오는 경로가 없어 위상 정렬할 수 있습니다. ㄴ과 ㄷ에는 방향 순환이 있으므로 위상 정렬할 수 없습니다. 따라서 ㄱ, ㄹ인 ②가 맞습니다.

콘텐츠 기록

콘텐츠 정보

자료 유형: 공개 기출
검수 상태: 자동 검사 완료
해설 작성·검수: 정처LAB 자동 검사
최종 검수: 자동 검사 완료

이 번호부터 전체 회차 풀기 내 오답 복습 회차 전체보기 시험별 CBT 안내

위상 정렬(topological sort)이 가능한 그래프만을 모두 고르면?

정답 2번

콘텐츠 정보

자료구조·알고리즘 복잡도 정리

같은 과목 학습 문제 12개