[백준 / 2252] 줄 세우기 ( 자바 )

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

 

전형적인 위상정렬 문제이다. 학교 수업의 커리큘럼을 짜거나 순서를 정할 때 유용하다.

A가 B보다 앞선다고 할 때 어떻게 코드로 표현할 것인가?

inDegree라는 배열을 만들어서 B에게 +1을 한다. 그렇다면 B앞에 1개가 있다고 선언하는 것이다.

그렇다면 B앞에 무엇이 있는 것인가? 이것은 List<Integer>[] 에 관리한다. 리스트 배열에서 A의 리스트에 B를 추가한다.

 

이전 문제에서는 B의 리스트에 A를 추가할 것인지, A리스트에 B를 추가할 것인지 헷갈렸다.

먼저 서있는 사람이 뒤에있는 사람들의 정보를 가지고 있어야 나중에 순서를 정할 수 있다.

다른 예로, 1학년은 자신이 들을 수 있는 과목들을 최대한 많이 가지고 있어야 이후의 커리큘럼을 짤 수 있다.

 

따라서 inDegree 배열과 List<Integer>[] 리스트배열의 관리만 잘 해주면된다.

inDegree 배열에서 값이 0인 것은 자신이 맨 처음에 시작할 수 있다는 것이다.

따라서 Queue안에서 계속 연결을 하면서 inDegree를 최신화하고, 마찬가지로 0인것을 계속 추가한다.

 

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] inDegree = new int[N+1];
		List<Integer>[] list = new ArrayList[N+1];
		for(int i=1;i<=N;i++)
			list[i] = new ArrayList<>();
		
		for(int i=0;i<M;i++) {
			int front = sc.nextInt();
			int back = sc.nextInt();
			
			list[front].add(back);
			inDegree[back]++;
		}
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1;i<=N;i++) {
			if(inDegree[i]==0) queue.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(!queue.isEmpty()) {
			int from = queue.poll();
			sb.append(from).append(" ");
			
			for(int to : list[from]) {
				inDegree[to]--;
				if(inDegree[to]==0) queue.add(to);
			}
		}
		
		System.out.println(sb.toString());
		
		
	}

}