줄 세우기(위상정렬)

줄 세우기

위상정렬이란?

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘이다.

여기서 보면 정보처리기사 합격하기 전에 4학년 되기가 되어야하고
4학년되기전에 대학생 되기가 수행되어야 한다.
이렇게 순서가 정해져 있을 때 사용하는 알고리즘이다.

문제에서 보면 학생 A가 학생 B 앞에 서야 한다.
즉 순서가 정해져 있다.

해법

위상 정렬을 해결하기 위해선 count배열이 중요하다.
즉

입력 기준으로 설명하자면

count => [0, 0, 0, 2]
즉 count배열이 다음과 같이 담길 것이다.
0인 것은 앞에 나와야 할 조건이 없다는 의미 이므로 사용될 수 있다.

그러면 1, 2가 사용될 수 있는데 이 때 Deque에 넣어주어서 다 한 번씩 돌게 한다. 그리고 해당 조건과 연결된 count배열을 1줄여준다.
즉 1 -> 3이라는 조건이 있으므로 3에서 1을 줄여준다.
또한 2 -> 3이란 조건에서 3에서 1을 줄여준다.
이렇게 하다보면 3의 조건은 0이 된다. 즉 조건이 없다는 의미이므로 deque에 넣어준다.

이렇게 deque 비어 있을 때까지 반복하고 남은 것을 마저 출력하면 된다.

코드

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());	
		
		int N, M;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int[] count = new int[N + 1];
		HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());	
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			count[end]++;
			
			if (graph.containsKey(start)) {
				ArrayList<Integer> list = graph.get(start);
				list.add(end);
				graph.put(start, list);	
			}
			else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(end);
				graph.put(start, list);	
			}
		}
		
		Deque<Integer> deque = new LinkedList<>();
		
		for (int i = 1; i < N + 1; i++) {
			if (count[i] == 0) deque.add(i);
		}
		StringBuilder sb = new StringBuilder();
		
		while(!deque.isEmpty()) {
			int cur_num = deque.pollFirst();
			
			sb.append(cur_num);
			sb.append(" ");
			if (!graph.containsKey(cur_num)) continue;
			ArrayList<Integer> list = graph.get(cur_num);
			for(int num: list) {
				count[num]--;
				if (count[num] == 0) deque.add(num);
			}
		}
		
		for (int i = 1; i < N + 1; i++) {
			if (count[i] != 0) sb.append(i);
		}
		
		System.out.println(sb.toString());
	}

}