[TIL-53/240401] 위상 정렬

위상 정렬(Topological Sortin)

위상 정렬이란

• 순서가 있는 작업(방향이 있는)을 차례로 진행해야 할 때 순서를 결정해 주기 위해 사용하는 알고리즘
• 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것
• Ex) 대학 선수과목, 공장의 작업 순서, 요리 순서, ... 등

DAG

 

그래프

 

사전 지식

• 진입 차수: 특정 노드로 들어오는 간선의 개수
• 진출 차수: 특정 노드에서 나가는 간선의 개수

 

위상 정렬 Queue 구현

위상 정렬 방법(Queue 사용)

1. 진입 차수가 0인 모든 노드를 Queue에 삽입
2. Queue가 공백 상태가 될 때까지 반복 수행
   1. Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
      (연결된 노드의 진입 차수를 감소시킴)
   2. 새롭게 진입 차수가 0이 된 노드를 Queue에 삽입

Queue에서 꺼내지는 순서(Queue에 들어오는 순서)가 정렬을 수행한 결과

의사코드 넣기

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 위상정렬_Queue {
	public static String[] cook = { "", "재료구매", "양념장만들기", "고기재우기", "고기손질", "제육볶음만들기", "식사", "뒷정리", "채소손질", "밥하기" };

	public static void main(String[] args) {
		Scanner sc = new Scanner(input);
		int V = sc.nextInt(); // 정점의 수
		int E = sc.nextInt(); // 간선의 수 -> 방향 있음

		int[][] adj = new int[V + 1][E + 1]; // 정점의 번호가 1번부터 시작
		int[] degree = new int[V + 1]; // 진입 차수 저장

		for (int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();

			adj[A][B] = 1; // 가중치가 따로 없기 때문에 1로 표기(선이 있다), 유향이니 반대는 처리 x
			// 진입 차수를 증가
			degree[B]++;
		}

		Queue<Integer> q = new LinkedList<>();

		// 큐로 위상 정렬 구현 1단계
		for (int i = 1; i < V + 1; i++) {
			if (degree[i] == 0)
				q.offer(i);
			// add와 offer의 차이: 예외를 발생시키냐(add) 안시키냐(offer0의 차이
		}

		StringBuilder sb = new StringBuilder();
		
		// 큐로 위상 정렬 구현 2단계
		while (!q.isEmpty()) {
			// 2-1. 하나 꺼냄
			int curr = q.poll();
			sb.append(cook[curr]).append("\n");
			// 2-2. 연결되어 있는 간선을 제거(말은 제거지만 실제로 제거하지 않음)
			for (int i = 0; i < V + 1; i++) {
				if(adj[curr][i] == 1) {
					degree[i]--; //진입 차수를 하나 깎는다.
					adj[curr][i] = 0; //실제로 간선을 삭제해버리는 것
					//2-3. 진입 차수가 새롭게 0이 되었다면 큐에 넣어
					if(degree[i] == 0) q.offer(i);
				}
			}

		}
		System.out.println(sb.toString());

	}

	static String input = "9 9\r\n" + "1 4\r\n" + "1 8\r\n" + "2 3\r\n" + "4 3\r\n" + "8 5\r\n" + "3 5\r\n" + "5 6\r\n"
			+ "9 6\r\n" + "6 7";

}

위상 정렬 Stack 구현

위상 정렬 방법(Stack 사용)

1. 진입 차수가 0인 모든 노드에서 DFS 탐색 수행
2. DFS 수행
   1. 해당 노드를 방문 표시
   2. 인접하면서 방문하지 않은 노드가 있다면 DFS 재귀 호출
   3. 함수 리턴 하기 전 Stack에 현재 노드 저장
3. Stack이 공백 상태가 될 때까지 pop

Stack에서 꺼내지는 순서를 뒤집으면 위상 정렬을 수행한 결과

import java.util.ArrayList;
import java.util.Stack;

class MyGraph {
	int vertexCnt;
	ArrayList<Integer>[] edge_List;
	boolean[] visit;
	boolean[] finish;
	Stack<Integer> answer;
	boolean cycle;
	
	public MyGraph(int N) {
		this.vertexCnt = N;
		edge_List = new ArrayList[N+1];
		for (int i = 0; i <= N; ++i) {
			edge_List[i] = new ArrayList<>();
		}
		visit = new boolean[vertexCnt+1]; //방문 표시
		finish = new boolean[vertexCnt+1]; //사이클 판단
		answer = new Stack<>(); //결과를 담을 스택
	}

	public void insert_Edge(int from, int to) {
		edge_List[from].add(to);
	}

	public void topological_Sort() {
		//방문하지 않은 정점을 DFS 수행
		for (int i = 1; i <= vertexCnt; ++i) {
			if (cycle) {
				System.out.println("그래프에 사이클 존재");
				return;
			}
			if (!visit[i]) {
				dfs(i);
			}
		}
		
		//스택에 담긴 정점들을 출력
		while (!answer.isEmpty()) {
			System.out.print(answer.pop() + " ");
		}
	}
	
	public void dfs(int v) {
		visit[v] = true;
	
		for (int i = 0; i < edge_List[v].size(); ++i) {
			int nv = edge_List[v].get(i);
			
			//방문하지 않았으면 dfs 수행
			if (!visit[nv]) {
				dfs(nv);
			} 
			//방문한 정점인데 finish 체크가 되지 않았으면 사이클이 존재한다는 의미
			else if (!finish[nv]) {
				cycle = true;
				return;
			}
		}
		
		//더 이상 갈 곳이 없는 정점을 finish 체크 & 스택에 넣어줌 (말단부터 상위로)
		finish[v] = true;
		answer.push(v);
	}
}

public class 위상정렬_DFS {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(7);
		mg.insert_Edge(1, 2);
		mg.insert_Edge(1, 3);
		mg.insert_Edge(1, 4);
		mg.insert_Edge(2, 5);
		mg.insert_Edge(2, 6);
		mg.insert_Edge(3, 7);
		mg.insert_Edge(3, 6);
		mg.insert_Edge(4, 3);
		mg.insert_Edge(6, 5);
		mg.topological_Sort();
	}
}

 

 

위상 정렬 특징

• 모든 정점을 방문하기 전에 Queue가 공백 상태가 되면 사이클이 존재하는 것
  (사이클이 존재하면 진입 차수가 0이 될 수 없음)
• 그래프의 유형은 DAG
• 여러 해답이 존재 가능
  (진입 차수가 0인 값이 동시에 생성이 된다면 작성한 코드 방법에 따라 답이 달라짐)
• 시간 복잡도 O(V+E)