[백준 2252] 줄 세우기

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

 

그래프의 위상 정렬 문제입니다.

위상정렬의 자세한 내용은 추후에 따로 올리도록 하고 일단 과정은

1. 자신을 가리키는 간선이 없는 정점을 찾아 큐에 넣음

2. 큐에서 빼어 (current)   current에서 가리키는 정점(next)를 찾아 

   그 정점의 간선 카운트를 줄이고 이게 0이라면 큐에 넣음.

 

	public class Q2252 {
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer st;
	st = new StringTokenizer(br.readLine());
	int student = Integer.parseInt(st.nextToken());
	int edge = Integer.parseInt(st.nextToken());
	int[] edgeCnt = new int[student+1];
	ArrayList<Integer>[] arr = new ArrayList[student+1];
	for(int i=0; i<arr.length; i++) {
	arr[i] = new ArrayList<Integer>();
	}
	for(int i=0; i<edge; i++) {
	st = new StringTokenizer(br.readLine());
	int num1 = Integer.parseInt(st.nextToken());
	int num2 = Integer.parseInt(st.nextToken());
	//num1 -> num2 (진입차수를 늘려줌)
	edgeCnt[num2]++;
	arr[num1].add(num2);
	}
	Queue<Integer> queue = new LinkedList<Integer>();
	for(int i=1; i<edgeCnt.length; i++) {
	if(edgeCnt[i]==0) {
	queue.add(i);
	}
	}
	for(int i=0; i<student; i++) {
	int current = queue.remove();
	bw.write(current+" ");
	int next;
	for(int j=0; j<arr[current].size(); j++) {
	next = arr[current].get(j);
	edgeCnt[next]--;
	if(edgeCnt[next]==0) {
	queue.add(next);
	}
	}
	}
	bw.flush();
	bw.close();
	}
	}

view raw Q2252.java hosted with ❤ by GitHub