[JAVA] 위상정렬 (Topology Sort) 알고리즘

질문 및 이론

밑의 질문에 대한 답을 역으로 사용해서 위상 정렬 문제인지 판별해라

요약: DAG인가? 선후 관계를 활용하는 문제인가? 순서를 정하는 문제인가?

Q) 기본 개념

선행 노드가 없는 노드들부터 탐색을 하고 후행 노드들과의 edge를 끊은 다음 순서에 넣어준다. 모든 선행 노드와의 edge가 끊긴 후행 노드를 queue에 추가해 탐색을한다.

Q) 어떤 조건에서 사용하는가?

• 유형 (방향이 있는) 그래프
• 싸이클이 없음
• 즉 DAG (Directed Acyclic Graph)

Q) 어떤 문제들에서 사용하는가?

• 선후관계가 정의된 그래프 구조에서 정렬
• 순서가 정해져 있는 작업들의 목록들을 가지고 전체 작업 순서를 결정
• 응용 :
  • 어떤 일을 처리할 때 다른 일들이 처리 되어있어야한다, 이럴 때 일을 진행하는 순서
  • 백준 2252번 문제 : 두 학생의 키 비교밖에 모를 때 키 순으로 정렬시키기

Q) 어떤 정보를 알고있나?

• 그래프 정보
  • 노드 갯수, 간선 갯수
  • 엣지 주어지는건 그때 그때 다른듯.. 사실 많이 안풀어봄
    • 지금까지 본거는 그냥 a -> b 이런 느낌으로 앞으로 오는 노드, 뒤에 오는 노드 쌍으로 준다

Q) 어떤 자료구조들이 사용되나?

• int[] degree : 해당 노드에 연결되어 있는 부모 노드의 갯수 a.k.a 이전에 해결되어야하는 작업의 수
• List<Integer>[] graph : 인접 리스트로 구현된 그래프
  • graph[i].get(j) : i는 j전에 선행되어야 하는 일, 또는 graph에서 i -> j 모양
• Queue<Integer> q : degree가 0인 노드들을 담는 큐

Q) 시간 복잡도는?

• O(V+E) : degree 구하는데 모든 V를 탐색한 후, 모든 E를 탐색해서 정렬을 찾음

풀이 방식

1. 그래프 입력을 받을 때 선행 노드 front와 후행 노드 back을 가지고
   1. graph[front].add(back); 으로 그래프 초기화
   2. degree[back]++; 으로 후행 노드에 연결되어 있는 부모 노드 갯수 증가
2. Queue에 degree가 0인것들을 먼저 넣어준다
3. Queue가 empty될 때 까지 순회
4. 노드를 poll한다
5. 그래프에서 해당 노드에 연결되어 있는 후행 노드들을 탐색한다
   1. 후행 노드의 degree를 1 감소시킨다
      1. 선행 노드 처리가 완료 되었으니 edge를 끊는 것과 비슷한 원리라고 보면된다
   2. 만약 후행 노드의 degree가 0이 된다면 모든 선행 노드의 탐색이 완료된 것으로 q에 추가해준다.

Java 코드 구현

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	static int N, M;
	static int[] degree;
	static List<Integer>[] graph;
	
	public static void main(String[] args) throws IOException {
		N = nextInt();
		M = nextInt();
		
		degree = new int[N+1];
		graph = new List[N+1];
		for(int i=0;i<graph.length;i++) {
			graph[i] = new ArrayList<>();
		}
		
		for(int m=0;m<M;m++) {
			int front = nextInt();
			int back = nextInt();
			
			graph[front].add(back);
			degree[back]++;
		}
		
		topologySort();
		
		System.out.println(sb.toString());
	}
	
	public static void topologySort() {
		Queue<Integer> q = new LinkedList<>();
		for(int i=1;i<degree.length;i++) {
			if(degree[i]==0) {
				q.add(i);
			}
		}
		
		while(!q.isEmpty()) {
			int node = q.poll();
			
			sb.append(node).append(" ");
			
			for (int connNodes:graph[node]) {
				if(--degree[connNodes]==0) {
					q.offer(connNodes);
				}
			}
		}
	}
	
	public static int nextInt() throws IOException {
		if(st==null || !st.hasMoreElements())
			st = new StringTokenizer(br.readLine());
		return Integer.parseInt(st.nextToken());
	}
}