BOJ - 2252 ) 줄 세우기

 

---

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

2252번: 줄 세우기

 

---

 

위상 정렬 ( Topology Sort )는 그래프의 진입 차수를 기준으로 다음 올 그래프의 순서를 정하는 

 

정렬알고리즘이다. 먼저 위상 정렬의 순서는 다음과 같다.

 

1. 그래프에서 진입차수가 0인 노드들을 큐에 넣는다.

 

2. 큐에서 하나씩 poll 하면서, 그 노드와 연결된 그래프들의 진입차수를 -1해준다 

( 큐에서 poll 한 노드는 이미 진입차수가 0 이고, 이는 정렬이 끝난것을 의미하므로 그와 연결된것을 처리한다.)

 

3. 진입차수를 줄일때 0이된다면 그 노드도 큐에넣는다.

 

4. 1-3번을 큐가 빌때까지 반복한다

 

5. 위상정렬이 되었다.

 

* 위상정렬의 조건은 DAG ( Directed Acyclic Graph) 를 만족해야한다. 즉 방향이 있으며 싸이클이 없어야한다.

 

만약 싸이클이 있다면 전체노드를 방문하지 않았는데 큐가 먼저 끝나는 상황이 나오거나

indegree배열이 음수가되는 상황이 나올수있다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int indegree[] = new int[n];
		boolean visit[] = new boolean[n];
		ArrayList<Integer> al[];
		ArrayList<Integer> result = new ArrayList<>();
		al = new ArrayList[n];
		for(int i = 0 ; i < n ; i ++) {
			al[i] = new ArrayList<>();
		}
		for(int i = 0 ; i < m ; i ++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken())-1;
			int e = Integer.parseInt(st.nextToken())-1;
			al[s].add(e);
			indegree[e]++;
		}
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		for(int i = 0 ; i < n ; i ++){
			if(indegree[i]==0) {
				dq.add(i);
				visit[i] =true;
			}
		}
		
		while(!dq.isEmpty()) {
			int now = dq.poll();
			result.add(now);
			for(int i = 0 ; i < al[now].size(); i++) {
				int cur = al[now].get(i);
				indegree[cur]--;
				if(indegree[cur] ==0) {
					dq.add(cur);
					visit[cur] = true;
				}
			}
		}
		
		for (Integer integer : result) {
			System.out.print((integer+1) +" ");
		}
		for( int i = 0 ; i < n ; i ++) {
			if(!visit[i]) System.out.print((indegree[i]+1)+" ");
		}
	}
}

---