위상 정렬 알고리즘: 그래프 이론과 큐 활용

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)로 효율적 → 대규모 그래프 작업에 적합