[JAVA] 위상 정렬 알고리즘 - 정렬 알고리즘 <Topological Sort>

위상 정렬 알고리즘

 

위상 정렬(Topological Sort)은 방향을 가진 그래프에서 간선으로 주어진 정점간의 선후 관계를 위배하지 않도록 나열하는 정렬 방법이다.

 

정점간의 선후 관계를 알기 위해서는 그래프의 개념 중 진입 차수(Indegree)와 진출 차수(OutDegree)를 잘 알고있어야 하는데, 간단하게 설명해보자면 우선 그래프에는 차수라는 개념이 있다. 

 

차수란, 그래프 상에 존재하는 정점과 그들 사이의 간선이 있을 때, 특정 정점에 연결된 간선의 개수를 의미한다.

따라서 차수는 다음 2가지로 나눌 수 있다.

진입 차수: 해당 정점으로 들어오는 간선의 개수
진출 차수: 해당 정점에서 다른 정점으로 뻗어나가는 간선의 개수

 

자, 이제 차수에 대해서 간단하게 알아보았으니, 이 차수로 정점간의 선후 관계를 어떻게 파악하는지 감을 잡아보자.

 

A -> B -> C

이렇게 연결된 그래프가 있다고 해보자. 이 그래프에 대한 차수를 정리해보면,

A는 0개의 진입 차수, 1개의 진출 차수,

B는 1개의 진입 차수, 1개의 진출 차수,

C는 1개의 진입 차수, 0개의 진출 차수를 가진다.

 

지금은 다른 걸 생각하지 말고 B를 먼저 정렬한다고 가정해보자.

 

B를 정렬한 상태로 A나 C를 넣게 되면, 그래프의 흐름에 위배되는 것을 알 수 있다.

 

A는 B노드로 향하고 있는데, B 노드가 먼저 정렬된다면, A노드는 평생 방문할 수 없게 된다.

 

따라서 여기서 생각해볼 수 있는 건, 특정 노드를 정렬하려면 그 노드로 향하고 있는 다른 노드들을 먼저 정렬해주어야 한다는 점이다.

 

대학교의 수강 신청 시스템을 생각해보자.

 

이산수학 1, 이산수학 2, 이산수학 3

 

이산수학 2 과목을 수강하려면, 선수과목인 이산수학 1을 먼저 수강해야 한다.

이산수학 3 과목을 수강하려면, 선수과목인 이산수학 2를 먼저 수강해야 한다.

 

따라서 선수과목이 필요 없는 이산수학 1 과목을 먼저 수강하고 이후에 2, 3을 수강해야 한다.

 

이 개념이 바로 위상정렬이다.

 

개념도 비교적 간단하고 구현 자체도 간단하다.

 

하지만, 여기서 끝낸다면 완전한 위상정렬이라고 할 수는 없다.

아직 알아야 할 개념들이 더 있다.

 

위상 정렬 속 사이클

위상 정렬을 해야하는 그래프에서 만약 A -> B, B -> C, C -> A, B -> D 와 같이 특정 부분에서 사이클이 존재한다고 가정했을 때,

A가 먼저 정렬되려면 B가 먼저 정렬되어야 하고, B가 먼저 정렬되려면 또 C가 먼저 나와야 하고 마찬가지로 C도 A가 먼저 나와야하기 때문에 선후 관계에서의 모순이 존재하게 된다.

 

그리고 이러한 사이클이 존재하지 않는 방향 그래프를 DAG(Directed Acyclic Graph)라고 한다.

왜 Indegree가 0일 때 큐에 추가할까?
위상 정렬의 개념에 따라서, 선후 관계 조건을 만족하는 정점을 먼저 정렬시켜야 하는데, 그 선후 관계 조건이라는 게
A가 정렬되기 위해서는 B가 먼저 정렬되어야 함과 같은 조건임.
따라서 A가 정렬되려면, A로 들어가는 모든 간선들을 없애거나 처리한 뒤에야 A를 정렬 시킬 수 있다는 말
이 말이 곧 진입 차수(Indegree)가 0임을 시사하는 부분

 

결국 위상 정렬은

• DAG(Directed Acyclic Graph)에서만 가능한 정렬 방법이다.
• 핵심 아이디어는 진입 차수(Indegree)가 0인 정점부터 차례로 꺼내어 정렬하는 것.
• 정점을 꺼낼 때마다 해당 정점에서 나가는 간선을 제거하고, 그 결과 진입 차수가 0이 된 정점을 큐에 넣는다.
• 큐가 빌 때까지 반복하며, 모든 정점을 처리했다면 성공적으로 위상 정렬이 끝난다.
• 만약 처리 도중에 큐가 비었는데 아직 정점이 남아 있다면 → 사이클 존재로 인해 위상 정렬 불가.

즉, 한마디로
“선수 조건이 없는 작업(Indegree=0)부터 처리하면서, 그 작업이 끝나면 다음 가능한 작업을 이어서 처리하는 과정”

라고 할 수 있겠다.

 

위상 정렬 동작 원리

 

1. 맨 처음 모든 간선을 읽으며 Indegree 테이블 채우기
2. Indegree가 0인 정점들을 모두 큐에 넣기
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4. 해당 정점으로부터 연결된 모든 정점의 Indegree 값을 1 감소시킴.
4-1. 이때 만약 Indegree가 0이 되었다면 그 정점을 큐에 추가
5. 큐가 빌 때까지 3번, 4번 과정을 반복

 

코드 전문

SWEA 1267 - 작업순서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_1267 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int V = Integer.parseInt(st.nextToken()); // 정점 개수
			int E = Integer.parseInt(st.nextToken()); // 간선
			
			Queue<Integer> q = new LinkedList<>(); // BFS를 돌기 위한 큐
			ArrayList<Integer>[] adj = new ArrayList[V + 1]; // 인접 리스트
			ArrayList<Integer> result = new ArrayList<>(); // 위상 정렬 결과를 담을 리스트

            for (int i = 0; i <= V; i++) {
                adj[i] = new ArrayList<>(); // adj[0]은 zero-index
            }
			int[] deg = new int[V + 1]; // Indegree를 저장할 배열, 진입 차수
			
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= E; i++) {
				int vertex = Integer.parseInt(st.nextToken());
				int node = Integer.parseInt(st.nextToken());
				adj[vertex].add(node); // 인접 리스트에 관계 저장
				deg[node]++; // 진입 차수 증가
			}
			
			for (int i = 1; i <= V; i++) {
				if (deg[i] == 0) q.add(i); // 진입 차수가 0인 노드부터 add
			}
			
			while(!q.isEmpty()) {
				int cur = q.poll();
				result.add(cur);
				for (int next : adj[cur]) {
					deg[next]--;
					if (deg[next] == 0) {
						q.add(next);
					}
				}
			}
			
			StringBuilder sb = new StringBuilder();
			sb.append("#").append(test_case).append(" ");
			
			for (int i = 0; i < V; i++) {
				sb.append(result.get(i)).append(" ");
			}
			
			System.out.println(sb);
		}

	}

}

 

코드 해설

 

	int V = Integer.parseInt(st.nextToken()); // 정점 개수
	int E = Integer.parseInt(st.nextToken()); // 간선
			
	Queue<Integer> q = new LinkedList<>(); // BFS를 돌기 위한 큐
	ArrayList<Integer>[] adj = new ArrayList[V + 1]; // 인접 리스트
	ArrayList<Integer> result = new ArrayList<>(); // 위상 정렬 결과를 담을 리스트

    for (int i = 0; i <= V; i++) {
    	adj[i] = new ArrayList<>(); // adj[0]은 zero-index
    }
    int[] deg = new int[V + 1]; // Indegree를 저장할 배열, 진입 차수

단순 입력은 생략하고, 위 부분부터 살펴보자.

 

정점 개수(V)와 간선의 개수(E)를 입력 받고, 정점들간의 관계를 정의하기 위한 인접 리스트 배열(adj)를 선언,

정렬 결과를 담을 리스트(result)를 선언한다.

 

이후 인접 리스트 배열의 각 행을 초기화 해준다.

이제 정점들간의 관계를 정의해야 하는데, 진입 차수를 저장할 배열(deg)도 생성해준다.

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= E; i++) {
            int vertex = Integer.parseInt(st.nextToken());
            int node = Integer.parseInt(st.nextToken());
            adj[vertex].add(node); // 인접 리스트에 관계 저장
            deg[node]++; // 진입 차수 증가
        }

        for (int i = 1; i <= V; i++) {
            if (deg[i] == 0) q.add(i); // 진입 차수가 0인 노드부터 add
        }

이제 입력에서 주어지는 정점들을 방향성에 유의하며 인접 리스트에 저장해준다.

현재 상황의 경우 vertex 노드에 node라는 정점을 연결 시켜준 것이다. (vertex ->  node, 방향성에 유의하자)

이후 node는 진입 차수가 하나 생겼으니 증가시켜 준다.

 

그 이후에는 진입 차수가 0인 노드들부터 먼저 큐에 넣어준다.

왜?
-> 기본 골자가 진입 차수가 0인 노드들을 먼저 정렬시키기 때문.
그래야만 선후 관계에 위배되지 않을 수 있음.
만약 진입 차수가 0인 노드가 존재하지 않는다면, 그 그래프에서는 사이클이 존재하는 것.

 

        while(!q.isEmpty()) {
            int cur = q.poll();
            result.add(cur);
            for (int next : adj[cur]) {
                deg[next]--;
                if (deg[next] == 0) {
                    q.add(next);
                }
            }
        }

핵심 로직이다.

 

기본적으로는 BFS로 정점들을 탐색한다.

큐에서 정점을 하나 꺼내고 해당 정점을 정렬 결과에 추가한다.

(이때 큐에 담긴 정점은 최소값임이 보장이 된다.)

 

그리고 방금 꺼낸 그 정점과 연결된 모든 정점들의 진입 차선(deg)을 감소시켜준다.

그 이유는, 현재 꺼낸 정점은 이미 정렬이 되었기 때문에 해당 정점과 연결된 모든 정점들의 간선을 지워줘야 하기 때문.

여기서 말하는 간선은 바로 진입 차선이다.

 

A -> B -> C 일 때,

진입 차선이 0 인 A를 먼저 정렬해주었고, A와 연결된 정점 B의 진입 차선을 감소시켜서 다음으로 큐에 들어갈 후보군을 만드는 것이다.

 

결국, 정점을 꺼내서 연결된 모든 정점의 진입 차선을 감소시켜주고 만약 감소시킨 그 정점의 진입 차선이 0이라면 큐에 넣고, 다음 탐색을 진행하게 된다.