백준 2252 - 줄 세우기 (JAVA 자바)

백준 2252 - 줄 세우기 (JAVA 자바)

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

 

문제집과 굉장히 유사한 문제입니다. 

문제집도 같이 풀어보시면 좋을 것 같습니다. 

PriorityQueue를 이용해서 풀면 됩니다. 

 

 

 

import java.util.*;
 
public class Main {
    
    static int n,m;
    static boolean visits[];
    static int indegree[];
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        indegree = new int [n+1];
        visits = new boolean[n+1];
        ArrayList <Integer> list [] = new ArrayList[n+1];
        
        for(int i=0; i<=n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        
        for(int i=1; i<=m; i++) {
            int tmp1 = sc.nextInt(); // 1 2
            int tmp2 = sc.nextInt(); // 3 3
            list[tmp1].add(tmp2);
            indegree[tmp2]++;
        }
        
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
        for(int i=1; i<=n; i++) {
            if (indegree[i]==0) {
                q.offer(i); // 1, 2가 들어감
            }
        }
        
        while(!q.isEmpty()) {
            int out = q.poll(); // 1, 2가 나옴
            System.out.print(out + " ");
            for(int i=0; i<list[out].size(); i++) {
                int next = list[out].get(i);
//                System.out.println("next값은 : " + next);
                indegree[next]--;
                if (indegree[next]==0) {
                    q.offer(next);
                }
            }
        }
    }
}