백준 2252 (줄 세우기)* - 위상순위 알고리즘

문제

---

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

 

 

 

 

 

풀이

---

위상정렬 알고리즘의 대표적인 문제다.

 

위상정렬이란?

어떤 일을 하는 순서를 찾는 알고리즘이다.

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것.

 

특징

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
• 위상 정렬의 과정에서 선택되는 정점의 순서를 위상순서(Topological Order)라 한다.
• 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단 되고 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 

알고리즘 순서

1. 진입 차수가 0인 정점(들어오는 간선수가 0인 점)을 선택

-> 진입 차수가 0인 정점이 여러개 존재할 경우 어느 정점을 선택해도 무방하다.

-> 초기에 간선의 수가 0인 모든 정점을 큐에 삽입

 

2. 선택된 정점과 여기에 부속된 모든 간선을 삭제

-> 선택된 정점을 큐에서 삭제

-> 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소

 

3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

 

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static List<Integer>[] list;
	static int[] countLink;
	static int n, m;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		list = new List[n+1];
		countLink = new int[n + 1];
		for(int i = 1 ; i <= n ; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[a].add(b);
			countLink[b]++;
		}
		topologicalSort();
		
		System.out.println(sb);
	}
	
	static void topologicalSort() {
		Queue<Integer> queue = new LinkedList<Integer>();
		
		for(int i = 1 ; i < n + 1 ; i++) {
			if(countLink[i] == 0)
				queue.add(i);
		}
		
		for(int i = 0 ; i < n ; i++) {
			int v = queue.remove();
			sb.append(v + " ");
			
			for(int next : list[v]) {
				countLink[next]--;
				
				if(countLink[next] == 0)
					queue.add(next);
			}
		}
	}
}