[BOJ 1766] 문제집 (Java)

#문제

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

1766번: 문제집

#풀이

위상정렬 알고리즘으로 풀 수 있다.

문제노드 간의 관계는 DAG(Directed Acyclic Graph) 로 표현될 수 있다. (방향성은 있으나 Cycle이 없는 것을 의미)

이 경우 indegree가 0인 Node부터 제거해가면서 순서를 정할 수 있다. 

0인 Node가 제거되면 해당 Node가 가리키고 있었던 인접 Node의 indegree를 감소시켜야 한다. 

이후 indegree가 0인 Node를 다시 찾아서 Queue에 넣는 것을 반복하다 보면 순서를 구할 수 있다.

가능하면 난이도가 쉬운 순인 조건이 있었기 때문에 Queue는 최소 힙을 사용하였다.

 

#소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1766 {

    public static int N, M;
    public static ArrayList<Integer>[] nodes;
    public static int[] indegs;
    public static void input() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nodes = new ArrayList[N+1];
        for(int i = 0; i <=N; i++){
            nodes[i] = new ArrayList<Integer>();
        }
        indegs = new int[N+1];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            // A -> B
            // 인접 노드 리스트를 만든다.
            nodes[A].add(B);
            // 노드의 indegree를 증가시킨다. 
            indegs[B]++;
        }
    }

    public static void pro(){
        // 동일한 조건에서 난이도가 쉬운게 우선이기 때문에 최소힙을 이용.
        PriorityQueue<Integer> que = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        // indegree 가 0인 노드를 큐에 넣는다. 즉 선행 문제가 없는 문제들. 
        for(int i = 1; i <= N; i++){
            if(indegs[i] == 0) que.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        while(!que.isEmpty()){
            int node = que.poll();
            sb.append(node + " ");
            
            //인접 노드를 조회해서 차수를 감소시킨다.
            for(int adj : nodes[node]){
                indegs[adj]--;
                if(indegs[adj] == 0){
                    // 차수가 0인 노드를 큐에 넣는다. 
                    que.offer(adj);
                }
            }
        }
        System.out.println(sb.toString());
    }


    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}