PS 위상 정렬
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- 알고리즘 이해 및 구현을 위한 중급 개발자
- 그래프 기반 작업 순서 결정 문제를 해결하는 학생 및 프로젝트 개발자
- 난이도: 중간 (그래프 이론, 큐 자료구조 이해 필요)
핵심 요약
- 위상 정렬은 방향성 그래프에서 진입차수(indegree)가 0인 노드부터 순차적으로 방문하는 알고리즘
- 사이클이 없는 그래프에서만 적용 가능 (큐가 비면 사이클 존재)
indegree
리스트와 큐 자료구조를 활용해 O(N + E) 시간 복잡도로 실행
섹션별 세부 요약
###1. 알고리즘 정의 및 목적
- 순서가 있는 작업(예: 수강신청)의 종속 관계를 해결하기 위한 알고리즘
- 방향성 그래프에서 노드 순서를 결정하는 방법
- 사이클 존재 여부 판단 가능 (큐가 비면 사이클)
###2. 핵심 개념
- 진입차수(indegree): 특정 노드로 들어오는 간선의 수
- 진출차수(outdegree): 특정 노드에서 나가는 간선의 수
- 노드 방문 조건: 진입차수가 0인 노드부터 우선 방문
###3. 알고리즘 단계
- 단계 1: 진입차수가 0인 노드를 큐에 삽입
- 단계 2: 큐가 비어질 때까지 반복 → 노드 추출, 인접 노드의 진입차수 1 감소, 0이 되면 큐에 삽입
- 단계 3: 결과 배열에 큐 삽입 순서 저장
###4. 예제 및 구현
- 예제 결과:
1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7
- 코드 구현:
deque
사용,indegree
배열 관리 - BOJ 2252 문제 적용: 학생 간 선수 조건을 그래프로 표현해 위상 정렬 적용
결론
- 사이클 검출과 작업 순서 결정에 유용 →
indegree
관리 및 큐 자료구조 활용 필수 - 시간 복잡도 O(N + E)로 효율적 → 대규모 그래프 작업에 적합