백준 2252번: 줄 세우기 [python]

tomkitcount·2025년 6월 22일

백준 알고리즘

매일 알고리즘

목록 보기

267/300

난이도 : 골드 2
유형 : 위상정렬
https://www.acmicpc.net/problem/2252

위상 정렬(Topological Sort) 개념 정리

1. 위상 정렬이란?

방향 그래프(DAG: Directed Acyclic Graph)에서 선행 관계를 지켜 노드를 정렬하는 알고리즘.

즉, 어떤 일들이 주어졌을 때 선행 조건이 있는 작업들을 순서대로 정렬하는 것.
예: "A를 하기 전에 B를 해야 한다"는 조건이 있으면 B가 A보다 앞에 나와야 함.

2. 기본 개념

진입 차수(in-degree): 한 노드로 들어오는 간선의 수.
큐(Queue)를 이용해서 진입 차수가 0인 노드부터 처리함.
처리한 노드와 연결된 간선을 제거 → 그로 인해 진입 차수가 0이 된 노드를 큐에 삽입.
위 과정을 반복해서 정렬된 결과를 얻는다.

3. 조건

사이클이 없어야 함 (그래서 DAG)
여러 정답이 나올 수 있음 (진입 차수가 0인 노드가 여러 개일 수 있으니까)

4. 알고리즘 흐름

1. 진입 차수 리스트 생성 (in_degree)
2. 인접 리스트(그래프) 생성
3. 진입 차수가 0인 노드를 큐에 삽입
4. 큐가 빌 때까지:
   - 큐에서 노드를 꺼내 결과 리스트에 저장
   - 해당 노드와 연결된 노드들의 진입 차수를 -1
   - 진입 차수가 0이 된 노드를 큐에 삽입