위상정렬이란?
위상정렬(Topological Sort)는 그래프와 관련된 알고리즘 중 하나로 선후관계가 정의된 그래프 구조에서 정렬하기 위해 사용한다.
1. 선후관계과 정의되어야 한다.
2. 그래프가 순환하지 않아야 한다.(DAG, Directed Acyclic Graph)
선후관계를 따진다면 이렇게 작성할 수 있다.
이때 노드를 방문하는 순서를 찾아야 한다면 위상 정렬을 사용할 수 있다. 참고로 결과 값은 여러 가지가 존재할 수 있다.
위상 정렬은 큐를 사용해서 구현한다.
-
그래프의 각 노드들의 진입 차수 테이블 생성 및 진입 차수 계산
-
진입 차수가 0인 노드 큐에 넣기 (이때 어떤 노드 먼저 시작하던지 관계없음)
-
큐에서 노드를 하나 꺼낸 후 꺼낸 노드와 간선으로 연결된 노드들의 진입 차수 감소 (진입 차수 테이블 갱신)
-
진입 차수 테이블을 갱신 후 진입 차수의 값이 0인 노드가 있다면 큐에 넣기 (없으면 아무것도 안 함)
-
3~4번의 순서를 큐에 더 이상 아무것도 없을 때까지 반복
만약 모든 순서가 끝났는데 진입 차수가 0이 아닌 노드가 있다면 그래프 내에서 순환이 존재한다고 볼 수 있다.
위의 그림을 따라서 본다면 결국 1, 7, 4, 3, 2, 8, 5, 6 순으로 정렬된다.
자바 코드로 구현하기
import java.util.*;
public class Main {
static int V, E; // V: 정점 개수, E: 간선 개수
static ArrayList<ArrayList<Integer>> graph; // 그래프를 저장할 인접 리스트
static int[] inDegree; // 각 정점의 진입차수를 저장할 배열
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정점의 개수 V와 간선의 개수 E 입력
V = sc.nextInt();
E = sc.nextInt();
// 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
}
// 진입차수 배열 초기화
inDegree = new int[V + 1];
// 간선 정보 입력
// A -> B 형태로 입력 (A를 선행으로 하는 B)
for (int i = 0; i < E; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
graph.get(A).add(B); // A에서 B로 가는 간선 추가
inDegree[B]++; // B의 진입차수 증가
}
// 위상정렬 수행
topologicalSort();
}
// 위상정렬 함수
static void topologicalSort() {
Queue<Integer> queue = new LinkedList<>(); // 진입차수가 0인 정점을 저장할 큐
ArrayList<Integer> result = new ArrayList<>(); // 위상정렬 결과를 저장할 리스트
// 진입차수가 0인 정점을 큐에 삽입
for (int i = 1; i <= V; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
// 큐가 빌 때까지 반복
while (!queue.isEmpty()) {
int current = queue.poll(); // 큐에서 정점 추출
result.add(current); // 결과 리스트에 추가
// 현재 정점과 연결된 모든 정점들의 진입차수를 1 감소
for (int next : graph.get(current)) {
inDegree[next]--;
// 진입차수가 0이 된 정점을 큐에 삽입
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
// 위상정렬 결과 출력
// 모든 정점을 방문하지 못했다면 사이클이 존재한다는 의미
if (result.size() != V) {
System.out.println("사이클이 존재합니다.");
return;
}
// 위상정렬 결과 출력
for (int vertex : result) {
System.out.print(vertex + " ");
}
}
}문제
알고리즘 [접근 방법]
학생들 간의 키 비교는 방향이 있는 그래프로 표현할 수 있다. A학생이 B학생보다 앞에 서야 한다는 것은 A->B로 표현된다. 선후관계가 있는 작업을 순서대로 나열하므로 위상정렬이 적합하다.
풀이방법
- 각 학생을 노드, 키 비교 정보를 간선으로 하는 방향 그래프를 만든다.
- 각 노드의 진입차수를 계싼한다.
- 진입차수가 0인 학생부터 위상정렬을 수행한다.
- 큐를 이용하여 순서대로 학생들을 나열한다.
풀이
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static ArrayList<ArrayList<Integer>> graph;
static int[] inDegree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// N: 학생 수, M: 키 비교 횟수
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 그래프 초기화
graph = new ArrayList<>();
for(int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
// 진입차수 배열 초기화
inDegree = new int[N + 1];
// 키 비교 정보 입력
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
graph.get(A).add(B); // A가 B앞에 서야 함
inDegree[B]++; // B의 진입차수 증가
}
// 위상정렬 수행
topologicalSort();
}
static void topologicalSort() {
Queue<Integer> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
// 진입차수가 0인 학생을 큐에 삽입
for(int i = 1; i <= N; i++) {
if(inDegree[i] == 0) {
queue.offer(i);
}
}
// 큐가 빌 때까지 반복
while(!queue.isEmpty()) {
int current = queue.poll();
sb.append(current).append(" ");
// 현재 학생과 연결된 다음 학생들의 진입차수 감소
for(int next : graph.get(current)) {
inDegree[next]--;
// 진입차수가 0이 되면 큐에 삽입
if(inDegree[next] == 0) {
queue.offer(next);
}
}
}
System.out.println(sb);
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M; // N: 학생 수, M: 키 비교 횟수
vector<vector<int>> graph; // 인접 리스트로 구현한 그래프
vector<int> inDegree; // 진입차수 저장 배열
void topologicalSort() {
queue<int> q;
// 진입차수가 0인 노드를 큐에 삽입
for(int i = 1; i <= N; i++) {
if(inDegree[i] == 0) {
q.push(i);
}
}
// 큐가 빌 때까지 반복
while(!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " "; // 현재 노드 출력
// 현재 노드와 연결된 모든 노드들의 진입차수를 1 감소
for(int next : graph[cur]) {
inDegree[next]--;
// 진입차수가 0이 된 노드를 큐에 삽입
if(inDegree[next] == 0) {
q.push(next);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// 입력 받기
cin >> N >> M;
// 그래프와 진입차수 배열 초기화
graph.resize(N + 1);
inDegree.resize(N + 1, 0);
// 키 비교 정보 입력
for(int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
graph[A].push_back(B); // A -> B 방향 간선 추가
inDegree[B]++; // B의 진입차수 증가
}
// 위상정렬 수행
topologicalSort();
return 0;
}정리
순서가 있는 그래프(방향 그래프)이고 순환관계가 없으면 위상정렬을 고려해보자.
시간 복잡도는 O(V+E)이다.
참고로 여러 가지 답이 가능할 수 있으며 모든 학생의 순서를 정확히 알 수 없어도 된다는 사실을 인지하자.
