[백준] 2252 줄 세우기 풀이 Java, 위상 정렬

2252번: 줄 세우기

 

 

 

★ 위상 정렬(Topological Sort)를 잘 모르면 아래 게시글을 보고 오는걸 추천드립니다.

위상 정렬(Topological sort) BFS,DFS

 

위상 정렬을 공부하고 한번 적용해보고 싶어서 푼 문제이기 때문에

위 게시글의 BFS 풀이법을 참고하면 아래 코드를 쉽게 이해할 수 있다.

 

import java.util.*;

public class Main {
	static int[] dp;
	static ArrayList<Integer>[] tree;
	static int[] visited;
	static int n;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		int m = scan.nextInt();

		int[] indegree = new int[n + 1];
		LinkedList<Integer>[] dag = new LinkedList[n + 1];

		for (int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();

			if (dag[a] == null)
				dag[a] = new LinkedList<Integer>();

			dag[a].add(b);
			indegree[b]++;
		}
	
    	// indegree가 0인 경우 Queue에 넣고 -1로 만들어 준다. (방문했다는 표시)
		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0) {
				queue.add(i);
				indegree[i]--;
				System.out.print(i + " ");
			}
		}

		// 인접한 노드의 indegree 값을 1씩 감소시키고 0인 경우 Queue에 넣는다.
		while (!queue.isEmpty()) {
			int num = (int) queue.poll();
			LinkedList<Integer> l = dag[num];

			if (l == null)
				continue;

			for (Integer i : l) {
				indegree[i]--;

				if (indegree[i] == 0) {
					queue.add(i);
					System.out.print(i + " ");
				}
			}
		}
	}

}