공부공간

BOJ - 2252 ) 줄 세우기 본문

알고리즘/위상정렬

BOJ - 2252 ) 줄 세우기

개발자가될수있을까? 2020. 3. 23. 20:52

 


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

 

2252번: 줄 세우기

첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다.

www.acmicpc.net

 


 

위상 정렬 ( 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)+" ");
		}
	}
}

 

'알고리즘 > 위상정렬' 카테고리의 다른 글

BOJ - 2056 ) 작업  (0) 2021.09.04
BOJ - 1766 ) 문제집  (1) 2020.11.08
BOJ - 1005 ) ACM Craft  (0) 2020.05.11
BOJ - 2623 ) 음악프로그램  (2) 2020.03.24
Comments