[BOJ] 백준 [2252] 줄 세우기 JAVA

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

2252번: 줄 세우기

문제

풀이

위상 정렬 문제이다. inDegree 배열을 하나 만든 다음 , 차수가 0이면 Queue에 추가 , 인접한 노드들의 InDegree 차수 1씩 감소 하는식으로 Queue가 비어 있을때 까지 반복하면 된다.

 
import java.util.*;
import java.io.*;
 
public class Main{
    static int V,E;
    static ArrayList<Integer>[] list;
    static int[] inDegree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]); E = Integer.parseInt(input[1]);
        list = new ArrayList[V+1];
        inDegree = new int[V+1];
        for(int i=1;i<=V;i++) {
            list[i] = new ArrayList<>();
        }
        for(int i=0;i<E;i++){
            input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            list[start].add(end);
            inDegree[end]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<=V;i++) {
            if (inDegree[i] == 0){
                q.add(i);
            }
        }
        LinkedList<Integer> answer = new LinkedList<>();
        while (!q.isEmpty()){
            int poll = q.poll();
            answer.add(poll);
 
            for (int e : list[poll]) {
                inDegree[e]--;
 
                if(inDegree[e] == 0 )
                    q.add(e);
            }
        }
        for (int e : answer) {
            System.out.print(e+" ");
        }
    }
 
}