[JAVA] 백준 1766번 : 문제집 (위상정렬)

www.acmicpc.net/problem/1766

문제

* 위상 정렬의 대표적인 문제이다.
(줄 세우기 문제에 약간 심화문제 우선순위 큐 사용)
yubh1017.tistory.com/manage/newpost/83?type=post&returnURL=https%3A%2F%2Fyubh1017.tistory.com%2F83

Queue를 이용한 위상정렬로 구현하였다. 

문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면

1. 위상 정렬은 그래프 정렬을 말한다.

2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다.

• 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며
• A->B 관계가 성립하면 B->A나 B->C->A와 같이 사이클이 생겨서는 안된다.

3. 자기 자신을 가리키는 간선의 갯수인 indegree 배열을 이용하여 구현할 수 있다.

4. 위상 정렬 과정

4.1) 위상 정렬을 위해 두개의 Queue를 만들어준다. 
q : indegree 값이 0인 노드들을 담기위한 Queue 
result: q에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue

4.2) 처음 indegree 간선의 갯수가 0인 index를 q에 넣어준다.

4.3) q가 empty일 때까지 while문을 돈다.
q.poll()한 노드를 result에 넣어준다.(result.offer(노드))
그리고 해당 노드에 연결된 노드의 간선의 갯수들을 지워주면서 간선의 갯수가 0이 되면 q에 넣어준다.

4.4) result에 담긴 node가 위상정렬 순서가 된다.

 

* 자세한 개념은 References에서 참고할 수 있으며 코드를 보고 이해 바랍니다.

 

References

위상 정렬 개념 : bcp0109.tistory.com/entry/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-Topological-Sort-Java?category=848939

 

해결 방안

문제 수 n이 정점(v)의 갯수가 되고 m은 간선(e)의 갯수가 될 것이다. 

따라서 이차원 ArrayList를 이용하여 단방향성 그래프를 생성해주고 가리킴을 받는 간선의 indegree[index]의 간선의 갯수를 증가해준다.

그리고 위상 정렬을 해준다.

여기서 3번 조건인 '가능하면 쉬운문제부터 풀어야한다.' 를 만족하기 위해 기존의 q에서 pq(우선순위큐)로 바꿔서 문제를 풀어준다. (문제는 난이도 순서로 출제되어 있기 때문에)

 

코드

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.Queue;

// 문제집
// 우선순위 큐를 이용한 위상정렬2
// 가능하면 쉬운 문제를 먼저 풀어야 하며 난이도 순서로 문제가 출제되어있다. => 우선순위 큐를 사용
public class Main {

	static int n; // 문제 수
	static int m; // 조건(간선)
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		
		int[] indegree = new int[n+1];
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i=0; i<n+1; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		int a,b;
		for(int i=0; i<m; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			graph.get(a).add(b);
			indegree[b]++;
		}
		// === 입력 끝
		
		topologicalSort(indegree, graph);
	}
	
	static void topologicalSort(int[] indegree, ArrayList<ArrayList<Integer>> graph) {
		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 간선의 갯수가 0인것
		Queue<Integer> result = new LinkedList<>();
		
		for(int i=1; i<n+1; i++) {
			if(indegree[i]==0)
				pq.offer(i);
		}
		
		int node;
		while(!pq.isEmpty()) {
			node = pq.poll();
			result.offer(node);
			
			for(int i: graph.get(node)) {
				indegree[i]--;
				
				if(indegree[i]==0)
					pq.offer(i);
			}
		}
		
		while(!result.isEmpty()) {
			System.out.print(result.poll() + " ");
		}
	}

}