위상정렬

• 진입 차수 : 특정 노드로 들어오는 간선의 개수
  • 진입 차수가 0인 경우, 선행 조건이 없는 노드라고 한다.
• 진출 차수 : 특정 노드에서 나가는 간선의 개수

위상 정렬

• 순서가 있는 작업을 차례로 진행해야 할 때 순서를 정해주기 위해 사용하는 알고리즘
• 사이클 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것 ex) 공장의 작업 순서, 요리 순서 등...
• 선행 조건이 없는 노드의 경우, 순서의 중요도가 없다. → 위상 정렬의 방법은 여러 개가 존재한다.
• 여러 해법이 존재할 수 있다.
  (진입 차수가 0인 값이 동시에 생성이 된다면, 작성한 코드 방법에 따라 답이 달라진다.
• 시간 복잡도 O(V + E)

Queue 구현
Stack 구현

Queue 구현하기

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

Queue에서 꺼내지는 순서가 정렬을 수행한 결과이다.

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

public class 위상정렬1_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[][] adjArr = new int[V+1][V+1];
		int[] degree = new int[V+1]; // 진입차수 관리 배열 
		
		// 입력 
		for(int i = 0; i < E ; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			
			adjArr[A][B] = 1;
			degree[B]++; // 진입 차수를 하나 증가를 시켜줘야 한다. 
		}
		
		//위상 정렬 Queue 1단계 : 진입 차수가 0인 목록을 모두 삽입 
		Queue<Integer> queue = new LinkedList<>();
		
		// 0 번 배열은 사용하지 않기 때문에 자동적으로 0이 된다. 따라서, 1부터 시작을 해줘야 한다. 
		for(int i = 1; i <= V; i++) {
			if(degree[i] == 0) {
				queue.add(i);
			}
		}
		
		
		StringBuilder sb = new StringBuilder();
		
		//위상 정렬 Queue 2단계 : queue가 공백 상태가 될 때까지 뽑아내고, 
		//						간선 제거하고, 진입차수가 0이 되면 새롭게 큐에 넣는다. 
		
		while (!queue.isEmpty()) {
			int curr = queue.poll(); // 이번에 처리해야 하는, 위상 정렬의 정렬 대상 
//			System.out.println(cook[curr]);
			sb.append(cook[curr]).append("\n");
			
			for(int i = 1; i<= V; i++) {
				if(adjArr[curr][i] == 1) { // 방향이 존재하기 때문에, 배열 안에 들어가는 순서가 중요하다 
					degree[i]--; // 진입 차수를 하나 깎아준다. 
					adjArr[curr][i] = 0;
					if(degree[i] == 0) {
						queue.add(i); // 차수가 0이 된다면, 다시 queue에 넣어준다. 
					}
				
				}
			}
		}
		
		System.out.println(sb);
	}
	
}

Stack 구현하기

• 진입 차수가 0인 모든 노드에서 DFS 탐색 수행

1. DFS 수행
   a. 해당 노드를 방문 표시
   b. 인접하면서 방문하지 않은 노드가 있다면 DFS 재귀 호출
   c. 함수 리턴하기 전 Stack에 현재 노드 저장
2. stack이 공백 상태가 될 때 까지 pop

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

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

public class 위상정렬2_stack {

	public static String[] cook = { "", "재료구매", "양념장만들기", "고기재우기", "고기손질", "제육볶음만들기", "식사", "뒷정리", "채소손질", "밥하기" };
	static int V,E;
	static int[][] adjArr;
	static int[] degree;
	static boolean[] visit;
	static Stack<Integer> ans;
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(input);
		
		V = sc.nextInt();
		E = sc.nextInt();
		
		adjArr = new int[V+1][V+1];
		degree = new int[V+1]; // 진입차수 관리 배열 
		visit = new boolean[V+1];
		
		ans = new Stack<>();
		
		// 입력 
		for(int i = 0; i < E ; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			
			adjArr[A][B] = 1;
			degree[B]++; // 진입 차수를 하나 증가를 시켜줘야 한다. 
		}
		
		for(int i = 1; i <= V ; i++) {
			if(degree[i] == 0) dfs(i);
		}
		
		while(!ans.empty()) {
			System.out.println(cook[ans.pop()]);
		}
		
	}
	
	
	
	
	
	private static void dfs(int curr) {
		visit[curr] = true;
		
		// 방문을 했다고 해서, 무조건 출력을 해서는 안 된다. 
		// 아직 선행 조건이 남아있을 수도 있기 때문에 
		
		for(int i = 1; i < V+1; i++) {
			if(adjArr[curr][i] == 1 && !visit[i]) {
				dfs(i);
			}
		}
		
		ans.push(curr); // 연결이 되어있는 모든 정점을 다 방문 후 입력 
		
	}
	
}