백준 1766 문제집

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

1766번: 문제집

위상정렬문제.
solved.ac 문제 목록 보다가 위상정렬 알고리즘 문제가 있길래 공부하고 풀어보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
		static int N,M; 
		static ArrayList<ArrayList<Integer>> list; // 인접 리스트
		static int [] edgeCount;
		static StringBuffer sb;
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			edgeCount = new int[N+1];
			list = new ArrayList<>();
			for(int n=0;n<=N;n++) {
				list.add(new ArrayList<>()); 
			}
			for(int m=0;m<M;m++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				list.get(from).add(to); // 시작점 -> 도착점 edge
				edgeCount[to]++; // 도착점 간선수 ++
			}
			sb = new StringBuffer();
			// 위상정렬
			// 차수가 0인경우 (다른 노드에서 오는 간선이 없는경우)
			PriorityQueue <Integer> pq = new PriorityQueue<>();
			for(int i=1;i<=N;i++) {
				if(edgeCount[i]==0) { // 차수가 0
					pq.add(i);
				}
			}
			while(!pq.isEmpty()) {
				Integer node = pq.poll();
				sb.append(node).append(" "); // 꺼냈으니 추가 
				ArrayList<Integer> next = list.get(node); // 이 노드에서 출발하는 간선탐색
				for(Integer e : next) {
					edgeCount[e]--; // 해당 노드의 차수--
					if(edgeCount[e] == 0) { // 차수가 0이면
						pq.add(e);
					}
				}
			}
			System.out.println(sb);
		}
}

위상정렬 알고리즘을 설명해보자면.
1. 노드의 탐색 순서를 설정하기 위해 간선을 이어 준다.
2. 먼저 탐색해야할 노드가 없는 노드를 큐에 넣어준다
3. 큐에서 노드를 꺼낸다(탐색)
4. 꺼낸 노드에서 출발하는 간선을 없앤다
5. 다시 2부터 반복

-> 먼저 탐색할 것이 없는 노드는 큐에 넣고, 탐색하면서 해당 노드가 먼저 탐색해야 되는 경우를 뜻하는 간선을 지운다.

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

2252번: 줄 세우기

 

비슷하게 위상정렬 쓰는 문제는 2252번이 있다.