[JAVA] 백준 2252번 : 줄 세우기 (위상정렬)

www.acmicpc.net/problem/2252

문제

* 위상 정렬의 대표적인 문제이다.

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]의 간선의 갯수를 증가해준다.

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

// 줄 세우기
// 위상정렬 문제
// 단방향
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) {
		Queue<Integer> q = new LinkedList<>(); // 간선의 갯수가 0인 정점이 들어갈 곳
		Queue<Integer> result = new LinkedList<>(); // 순서에 대한 결과가 들어갈 곳
		
		for(int i=1; i<=N; i++) {
			if(indegree[i]==0)
				q.offer(i);
		}
		
		int current;
		while(!q.isEmpty()) {
			current = q.poll();
			result.offer(current);
			
			for(int i : graph.get(current)) {
				indegree[i]--;
				
				if(indegree[i]==0)
					q.offer(i);
			}
		}
		
		while(!result.isEmpty()) {
			System.out.print(result.poll() + " ");
		}
	}

}