위상 정렬 정리, 진입 차수로 선후 관계를 줄 세우는 카흔 알고리즘과 사이클 판별

자료구조를 들어야 알고리즘을 들을 수 있고, 라이브러리 A를 빌드해야 B를 빌드할 수 있습니다. 이렇게 먼저 해야 하는 일이 정해진 작업들을 모순 없이 한 줄로 세우는 것이 위상 정렬입니다. 정보처리기사 그래프 문제, 프로젝트 일정 관리(선후행 관계)와 연결되는 토픽입니다.

위상 정렬은 방향 그래프의 모든 간선 방향을 지키는 정점 순서

정의: 방향 비순환 그래프(DAG)에서 모든 간선 u → v에 대해 u가 v보다 앞에 오도록 정점을 나열하는 것입니다. 사이클이 있으면 위상 정렬은 존재하지 않습니다.

• 핵심 키워드: DAG, 진입 차수(In-degree), 카흔 알고리즘, DFS 후위 순서, 사이클 판별
• 결과는 하나가 아닐 수 있음: 동시에 시작할 수 있는 정점이 여럿이면 여러 정답이 가능합니다.

카흔 알고리즘은 진입 차수 0인 정점부터 꺼낸다

1. 모든 정점의 진입 차수(들어오는 간선 수)를 센다.
2. 진입 차수가 0인 정점을 큐에 넣는다.
3. 큐에서 정점을 꺼내 결과에 추가하고, 그 정점에서 나가는 간선을 지우며 도착 정점의 진입 차수를 1씩 줄인다.
4. 새로 진입 차수가 0이 된 정점을 큐에 넣고, 큐가 빌 때까지 반복한다.
5. 결과에 들어간 정점 수가 전체보다 적으면 사이클이 있는 것이다.

선수 과목 예시로 직접 따라가 보기

단계	꺼낸 정점	진입 차수가 0이 되어 큐에 들어간 정점
초기	–	이산수학, 프로그래밍
1	이산수학	없음(알고리즘은 아직 1)
2	프로그래밍	자료구조, 운영체제
3	자료구조	알고리즘, 데이터베이스
4	운영체제	네트워크
5	알고리즘	없음(인공지능은 아직 1)
6	데이터베이스	인공지능
7~8	네트워크, 인공지능	–

결과는 이산수학 → 프로그래밍 → 자료구조 → 운영체제 → 알고리즘 → 데이터베이스 → 네트워크 → 인공지능입니다(코드로 검산). 큐에 넣는 순서를 바꾸면 프로그래밍을 먼저 꺼내는 등 다른 정답도 가능합니다.

카흔 방식과 DFS 방식 비교

구분	카흔(Kahn, 1962)	DFS 기반
원리	진입 차수 0인 정점을 큐로 처리	DFS 종료 순서(후위)를 뒤집음
사이클 판별	처리된 정점 수가 V보다 적으면 사이클	탐색 중 방문 중인 정점을 다시 만나면(역방향 간선) 사이클
복잡도	O(V+E)	O(V+E)
장점	동시에 시작 가능한 작업 묶음을 단계별로 파악하기 쉬움	재귀로 간결하게 구현

답안에서 놓치기 쉬운 포인트

• 위상 정렬은 정렬 알고리즘(퀵·병합 정렬)과 무관한 그래프 알고리즘입니다.
• 무방향 그래프나 사이클이 있는 그래프에는 정의되지 않는다는 전제를 꼭 쓰세요.
• 활용: 빌드 시스템의 의존성 해결, 패키지 설치 순서, 스프레드시트 셀 재계산 순서, 프로젝트 일정의 선후행 관계(CPM 계산의 전 단계).

시험 직전 한 줄 요약

위상 정렬은 DAG에서 간선 방향을 지키는 정점 순서이며, 카흔 알고리즘은 진입 차수 0인 정점을 큐로 꺼내 O(V+E)에 구하고, 남는 정점이 있으면 사이클입니다.

학습용 정리이며 실제 시험 문항과 다를 수 있습니다. 출제 기준은 큐넷 공지를 확인하세요. 그림은 이해를 돕기 위한 개념도와 예시입니다.