위상정렬(topology) 알고리즘

위상정렬은 순서를 찾아주는 알고리즘이다. 

가령 정확한 순서를 모를 때 대략적인 순서를 만들어주는 알고리즘이다. 

우선 이 알고리즘은 선행과 후행이 나온다. 선행과목이 있어야 후행과목이 있는 것처럼 

쉽게 말해 순서가 주어진다. 

주어진 순서를 보고 

queue와 InDegree를 활용하는게 핵심인데 이것은 진입 차수다.

만약 

1->3 

2->4 

3->4

1->2이렇게 있으면 진입차수는 

1 2 3 4

0 1 0 2 

이다. 순서가 어떨진 모르겠지만 

진입차수가 0인 것은 내 앞에 어떤 것도 거칠 필요가 없다는 뜻이다. 그러니 queue에 제일 먼저 집어넣어준다.

queue ( 1, 3)

1이 들어온 후 1를 큐에서 빼주고 제일 먼저 순서에 넣는다.

순서 = 1

그리고 1에서 또 진입할 수 있는 녀석을 찾아준다. 1에서 진입하면 2로 진입이 가능하다. 

그럼 2를 또 큐에 넣어주고 진입차수를 -1해서 0이됨으로 큐에 넣어준다.

queue(3,2)

이 상황에서 3을 큐에서 빼주고 순서배열에 2번째로 넣고

순서 = 1 3 

3에서 진입가능한 사람을 찾아본다. 그럼 4가 나온다.하지만 4는 -1해도 진입차수가 1이 남기때문에 큐에 들어오지 않는다.

queue(2)

다시 큐에서 2를 빼준다. 2를 빼서 순서에 넣고 2에서 갈 수 있는 녀석을 찾아본다. 2에서 갈 수 있는 녀석은 4밖에 없다.

순서 1 3 2 

그럼 큐에 다시 4를 넣고

queue(4)

4를 다시 빼주고 4에서 진입가능한 녀석이 있나 살펴본다. 없다 . 그럼 끝나는 것이다. 

순서 1 3 2 4

주의해야할 점은 간혹 사이클이 만들어지는 위상정렬이 생기는데 , 이럴땐 순서 순서가 맞물리기 때문에 

웹툰 작가들 존경한다..

무튼 저런 상태면 while(!q.isEmpty())문에서 튕겨져 나와버린다.

이런 경우 사이클이 변수하나를 두고 변수가 모든 정점 갯수만큼 선회했는지를 알아보는 코드를 집어넣으면 된다 . 

이제 문제와 코드를 보자.

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class boj1197 {
	static int N, M, S;
	static int inDegree[],answer[];
	static ArrayList<ArrayList<Integer>> list;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);//학생 수 
		M = Integer.parseInt(s[1]);//비교 횟수
		inDegree = new int[N+1];
		answer = new int[N+1];
		list = new ArrayList<>();
		for(int i =0; i<=N; i++)list.add(new ArrayList<>());
		
		for(int i= 0; i<M;i++) {
			s =in.readLine().split(" ");
			int from = Integer.parseInt(s[0]);
			int to = Integer.parseInt(s[1]);
			list.get(from).add(to);
			inDegree[to]++;
		}
		Queue<Integer> q = new LinkedList<Integer>();
		int cnt =0;
		for(int i =1; i<=N;i++) if(inDegree[i]==0) q.add(i);
		
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			answer[cnt++]=cur;
			if(cnt==N)break;
			for(int j=0;j<list.get(cur).size();j++) {
				int next = list.get(cur).get(j);
				if(--inDegree[next]==0) q.add(next);
			}
		}
		if(cnt !=N)System.out.println("사이클 발생");
		for(int i =0; i<N;i++)System.out.print(answer[i]+ " ");
		System.out.println();
	}
}