위상 정렬 [개념]

cleanUrl: /위상-정렬

1. 위상 정렬이란?

• 위상 정렬은 영어로 Topological Sort라고 한다.
• Topology: 물리적인 배치의 형태. 주로 통신 네트워크의 구성이나 형태를 뜻함.

• 정점들의 연결성이나 연속성등을 정렬하는 것을 위상 정렬이라고 한다.

• 문명 5의 기술 트리를 생각하면 쉽다.
• 어떤 기술을 연구하려면 선행 기술이 필요하다.
• 예를 들어, ‘철기’를 연구하기 위해서는 ‘청동기’를 먼저 연구해야 한다.
• 이러한 선후 관계를 따라 기술을 연구하는 과정이 위상 정렬과 유사하다.

• 위상 정렬은 방향 그래프(Directed Acyclic Graph)에서만 수행이 가능하다.
• 즉, 위 그림의 C, D, F와 같이 사이클이 존재하면 정렬이 불가능하다.

2. 동작 방식

• 사이클이 없는 그래프의 위상정렬을 수행해보자.

• 위와 같은 그래프를 보기 좋게 정렬하면 아래와 같이 나온다.

• 모든 간선의 방향이 왼쪽에서 오른쪽으로 흘러가는 방향으로 되어 있다.

• 이제 하나하나 단계를 따라가며 위상 정렬을 해보자.

• 먼저 진입 차수(In-degree)가 0인 정점을 큐에 넣는다.
• 진입 차수: 해당 간선으로 들어오는 간선의 개수
• 진입 차수가 0인 정점을 알기 위해서는 모든 정점의 진입 차수를 알아야 한다.

• 그래프의 진입 차수가 0인 B를 큐에 삽입한다.

• B정점을 확인하여 B와 연결된 모든 정점의 연결 정보를 삭제한다.

• B의 간선들이 사라짐에 따라 B와 연결되어 있던 A, D의 진입 차수도 낮아진다.

• 사라진 B 정점을 제외하고 진입 차수가 0인 것을 큐에 삽입한다.

• 진입 차수가 낮아진 A와 D중 A만 진입 차수가 0이 되었기 때문에 0을 큐에 삽입하면 된다.

• 마찬가지로 A와 연결된 간선을 삭제하고 연결된 정점의 진입 차수를 낮춘다.

• C의 정점의 진입 차수가 0이 되었기 때문에 큐에 삽입한다.

• 그리고, C와 연결된 정점들의 진입 차수를 낮춰준다.

• C와 연결되어 있던 D와 E의 진입 차수가 1씩 줄어든다.

• D의 진입 차수가 0이 되었기 때문에 D를 큐에 넣어주고 진입 차수를 낮춰준다.

• D와 연결되어 있던 E, F의 간선이 사라진다.

• E와 F의 진입 차수도 1씩 줄어들게 된다.

• 진입 차수가 0인 E가 큐에 들어가게 된다.

• 이제 정점도 F 하나만 남게 된다.

• F도 더이상 들어오는 간선이 없기 때문에 진입 차수가 0이 된다.

• 이제 마지막 F 정점만 큐에 들어가면 더이상 남은 정점이나 간선이 없기 때문에 알고리즘이 종료되게 된다.

• 정점이 큐에 들어간 순서가 바로 위상 정렬의 순서가 된다.

3. 정리

• 알고리즘 순서
1. 진입 차수(In-degree)가 0인 정점을 큐에 삽입한다.
2. 큐에서 정점을 하나씩 꺼내고, 해당 정점과 연결된 간선을 제거한다.
3. 제거된 간선과 연결되어 있던 정점들의 진입 차수가 감소한다.
4. 간선 제거 이후 진입 차수가 0인 정점을 큐에 넣는다.
5. 큐가 빌 때까지 위 과정을 반복한다. 큐에서 꺼낸 순서가 정점의 위상 정렬 결과이다.

• 대표 문제
• https://www.acmicpc.net/problem/2252
• https://www.acmicpc.net/problem/1005
• https://www.acmicpc.net/problem/1766

참고 자료

위키독스03. 위상 정렬

03. 위상 정렬

# 위상 정렬 위상 정렬은 영어로 Topological Sort라고 합니다. 여기서 Topology는 물리적인 배치의 형태를 뜻합니다. 주로 통신 네트워크의 구성이나 형태를 뜻…

위키독스