Coding Test(Topological Sort)

위상 정렬(Topological Sort)

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열

선행 조건들을 만족하는 일의 수행 순서

특정 노드를 방문하려면, 조건으로 갖는 다른 노드들이 방문된 상태여야함

 

DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다

위상정렬에서 중요하게 쓰이는 개념인 진입차수와 진출차수

 

<Queue - 동작 과정>

1. 진입차수가 0인 모든 노드를 큐에 넣는다(진입차수가 0이라는건 시작점이라는 뜻)

2. 큐가 빌 때 까지 다음의 과정을 반복한다

     2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

     2-2) 새롭게 진입차수가 0이 된ㄷ 노드를 큐에 넣는다

=> 결과적으로 각 노드가 Queue에 들어온 순서가 위상 정렬을 수행한 결과와 같다

 

Ex) BOJ 2623 음악프로그램 - BFS로 푼 풀이

package pratice;

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

public class Main_2623_bfs {
	static int n,m;
	static List<Integer>[] board;
	static List<Integer> res;
	static int[] data;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
	
		board = new ArrayList[n+1];
		for (int i = 1; i <n+1; i++) {
			board[i] = new ArrayList<>();
		}
		
		data = new int[n+1];
		res = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			String[] input = br.readLine().split(" ");
			
			for (int j = 1; j < Integer.parseInt(input[0]); j++) {
				int from = Integer.parseInt(input[j]);
				int to = Integer.parseInt(input[j+1]);
				board[from].add(to);
				data[to]++; //진입차수 하나씩 늘리기, to에 ++해줘야 진입이라는 의미
				}
		}

		bfs();
		
		if(res.size() == n) {
			for(Integer num:res)
				System.out.println(num);
		}
		else
			System.out.println(0);
	}
	
	
	public static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		for (int i = 1; i < n+1; i++) {
			if(data[i]==0) //진입차수가 0인 애들부터 시작하겠다는 의미
				queue.add(i); 
		}
		
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			res.add(v);
			
			for(Integer num:board[v]) {
				data[num]--; //poll한 node랑 연결되어있는 애들을 한번 탐색했으니까 차수를 감소
				
				if(data[num]==0) //감소하고 진입차수가 0이 되었다는건 더이상 더 탐색할 곳이 없다는 의미
					queue.add(num);
			}
		}
		return;
		
		
	}

}

<Stack - 동작 과정>

1. 진입 차수가 0인 노드부터 DFS를 시작한다

2. 방문할 수 있는 인접 노드가 없다면 현재 노드를 stack에 저장한다

3. DFS가 종료되면, stack에 들어있는 노드를 하나씩 꺼내서 값을 출력