백준 1766 - 문제집 ( JAVA )

출처 - 백준 프로그램

1766번: 문제집

---

 

[Algorithm] 위상정렬(Topology Sort)

↑  위상정렬을 이용해서 구현하였다 . 

 

[ 알고리즘 ] 

List 를 담은 List 를 생성하였다 . 각 문제에 대하여 '이후에' 풀 수 있는 문제를 담고 있다. 

예를 들어, 문제 1 은 문제 3 이후에 풀 수 있기 때문에 list[3] = {1} 이다. 

 

count 일차원 배열에, 진입차수값을 저장하였다.

• 선행되어야 할 문제가 있다면, 해당 문제만큼 값 저장 
• 선행되어야 할 문제가 없다면 , 진입 차수 = 0 

쉬운 문제, 즉 숫자가 작은 문제 먼저 풀어야 하기 때문에 우선순위큐를 이용하였다. 

1. 진입 차수가 0 인 문제, 즉 선행되어야 할 문제가 없는 것 부터 우선순위큐에 넣는다 ( 3 ,4 ) 
2. 가장 첫번째의 값을 poll 한다. 우선순위큐에 의해 더 작은 값이 먼저 나온다.
3. 이후에 풀 수 있는 문제를 담은 list 를 탐색하며, 해당 문제의 진입 차수 값을 -1 한다. 
4. 진입차수가 0 인 된 문제가 있다면, 선행되어야 할 문제를 다 푼것이므로 큐에 넣는다. 
5. 반 - 복 

---

[ 코드 ]

import java.util.*;
import java.io.*;
 
public class Solution_BaekJoon_1766_문제집_골드2 {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder(); 
        StringTokenizer st ;
        
        String s= br.readLine();
        st= new StringTokenizer(s, " ");
        int N= Integer.parseInt(st.nextToken());
        int M= Integer.parseInt(st.nextToken());
        
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i=0; i<=N; i++) {
            list.add(new ArrayList<Integer>()); 
        }
        
        int[] count = new int[N+1]; //진입차수
        while(M-->0) {
            String s1= br.readLine();
            st= new StringTokenizer(s1, " ");
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken()); 
            list.get(a).add(b);
            count[b]++;
        }
    
        PriorityQueue<Integer> que = new PriorityQueue<>(); 
        for(int i=1; i<=N; i++) {
            if(count[i]==0) {
                que.add(i);
                count[i]=-1;
            }
        }
        
        while(!que.isEmpty()) {
            int now = que.poll(); // 더 작은 값 나오겠지 ? 
            sb.append(now).append(" ");
            
            List<Integer> nli = list.get(now);
            if(!nli.isEmpty()) {
                int size = nli.size();
                for(int i=0; i<size; i++) {
                    count[nli.get(i)]--;
                }
            }
            
            for(int i=1; i<=N; i++) {
                if(count[i]==0) {
                    que.add(i);
                    count[i]=-1;
                }
            }
        }
 
        System.out.println(sb);
    }
}
 

끗 !