난이도 : 골드 3
유형 : 위상정렬
https://www.acmicpc.net/problem/2252
위상정렬 유형의 첫 문제라 우선 위상정렬의 개념부터 정리하고 풀겠다.
위상정렬(Topological Sort) 이란
정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다.
어원
- Topological: "위상적인", "구조적인 관계에 기반한"을 의미
- Sort: "정렬"
즉, "위상 정렬"은 구조적인 순서 관계를 고려한 정렬을 의미하며, 단순한 수치 정렬이 아닌 "순서 관계(graph structure)"에 따른 정렬이다.
전제 조건
위상 정렬이 동작하려면 반드시 DAG(Directed Acyclic Graph)여야 한다.
| 조건 | 설명 |
|---|---|
| Directed | 방향성이 있는 간선으로 구성되어야 함 |
| Acyclic | 사이클(순환)이 없어야 함 (같은 노드를 다시 방문하는 경로 없음) |
진입차수, 진출 차수 라는 용어도 등장하는데 뜻은 다음과 같다.
진입 차수(Indegree) : 노드로 들어오는 간선의 수
진출 차수(Outdegree) : 노드에서 나가는 간선의 수
즉 진입, 진출의 주체는 간선이다.
위상 정렬 알고리즘 (Kahn’s Algorithm – BFS 기반)
- 모든 노드의 진입 차수(indegree)를 계산한다.
- 진입 차수가 0인 노드들을 큐에 삽입한다.
- 큐가 빌 때까지 반복한다:
- 큐에서 노드를 꺼내어 정렬 결과에 추가한다.
- 해당 노드에서 나가는 간선을 제거한다.
- 간선을 제거한 이후 진입 차수가 0이 된 노드를 큐에 삽입한다.
- 모든 노드를 방문했다면 위상 정렬이 완료된다.
- 그렇지 않다면 → 사이클이 존재하여 위상 정렬이 불가능하다는 의미
예시로 이 알고리즘을 보겠다.
이렇게 생긴 그래프가 있다.
사이클이 없고, 방향이 존재하니 DAG이므로 위상정렬이 가능하다.
- 모든 노드의 진입 차수를 계산한다.
- 진입 차수가 0인 노드들을 큐에 삽입한다.
1번 노드 만이 진입차수가 0이므로 1만 큐에 삽입된다.
큐에서 노드 1을 꺼내어 정렬결과에 넣고, 1에서 나가는 진출차수를 제거했다.
그리고 다시 진입 차수가 0이된 노드들을 큐에 삽입했다.
다시 2를 큐에서 꺼내 정렬결과에 넣고 2와 연결된 간선들을 다 제거해준뒤
진입차수가 0인 노드'3'을 큐에 넣는다.
이와 같은 방식을 반복했을 때
큐의 들어가는 노드 순서는
1-> 2 -> 5 -> 3 -> 4 -> 6 -> 7 이 되고
결국 큐에서 먼저 들어간 노드가 먼저 나오기에 정렬결과는 큐에 들어간 순서와 동일하게
1 -> 2 -> 5-> 3 -> 4 -> 6 -> 7 이 된다.
파이썬에서는 이를 deque 라이브러리의 .popleft() 메소드를 사용하여 구현한다.
이제 문제를 풀겠다.
문제 접근
학생들을 키순으로 줄을 세우는 데, 전체 키가 주어져있지 않고,
누가 더 큰 지 비교된 값만 주어졌을 때 키 순으로 출력하는 문제이다.
"A가 B보다 앞에 서야 한다"
이 말은 곧:
"A → B 방향의 관계가 생긴다"
(A가 먼저, B는 나중)
이기에 방향 그래프가 된다.
풀이 과정
- 그래프 인접 리스트를 만든다
- 각 노드의 진입 차수를 센다
- 진입 차수가 0인 노드를 큐에 넣고 시작
- 큐에서 노드를 꺼내고, 연결된 노드의 진입 차수를 줄인다
- 진입 차수가 0이 된 노드는 큐에 추가
- 이 과정을 반복하며 정렬된 결과 리스트를 만든다
해답 및 풀이
from collections import deque
import sys
input = sys.stdin.readline
# 입력 n: 학생 수 , m : 키 비교 횟수
n, m = map(int,input().split())
# 1. 그래프와 진입 차수 초기화
graph = []
for _ in range(n + 1):
row = []
graph.append(row)
indegree = [0] * (n+1)
# 2. 간선 정보 입력
for _ in range(m):
a, b = map(int,input().split())
graph[a].append(b)
indegree[b] += 1
# 3. 진입 차수 0 인 노드를 큐에 추가
queue = deque()
for i in range(1, n + 1):
if indegree[i] == 0:
queue.append(i)
# 4. 위상 정렬
result = []
while queue:
now = queue.popleft()
result.append(now) # 큐에서 꺼내 정렬결과에 담아줌
for neighbor in graph[now]:
indegree[neighbor] -= 1 # 진입차수 1 줄이기
if indegree[neighbor] == 0:
queue.append(neighbor)
# 5. 결과 출력
print(*result)뭔가 이 부분이 잘 이해가 되지 않았는데
for neighbor in graph[now]:
indegree[neighbor] -= 1 # 진입차수 1 줄이기
if indegree[neighbor] == 0:
queue.append(neighbor)graph는 2차원으로 이루어져있다.
graph[now]라는 것은
만약 now 가 4 라면
4-> 1
4-> 2 이런식으로 간선이 두개일 수 있으므로 for in 연산자를 사용하여 반복을 돌아 준 것이다
그러면 neighbor 는 1과 2가 되어 그 1과 2 노드들을 돌아주며 4에서 1과 2로 뻗어나오는 차수들을 제거해주고, 제거해줬을 때 진입차수가 0이 된다면 큐에 넣어주는 로직이다.
