[BOJ] 백준 1766 문제집

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

 Input 

4 2

4 2

3 1

 

 Output 

3 1 4 2

위상정렬 (Topological sort)

위상정렬 (Topological sort)

구현

- 인접리스트로 그래프 표현 

- 진입차수 방식의 위상정렬

- 사이클 유무 확인 필요 X

- 위상 정렬 결과가 여러개 나올 수 있지만,

   번호가 낮은 정점이 우선시 되므로 결과를 한 개로 제한.  → 우선순위 큐 이용

 

우선순위 큐

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
         
        // 정렬 전: 3 1 4 2
        pq.offer(3); pq.offer(1); pq.offer(4); pq.offer(2);
 
        // 정렬 후: 1 2 3 4
        while (!pq.isEmpty()) {
            bw.write(pq.poll() + " ");
        }
 
        bw.flush(); bw.close();
    }
}

---

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
    static ArrayList<ArrayList<Integer>> adList;
    static int N;
    static int[] indegree;
    static PriorityQueue<Integer> pq;
    static ArrayList<Integer> answer;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        N = Integer.parseInt(sc.next());
         
        adList = new ArrayList<>();
        adList.add(new ArrayList<>());
        indegree = new int[N+1];
         
        // 1~N까지의 각 정점을 리스트에 삽입
        for(int i=1; i<=N; i++) {
            adList.add(new ArrayList<>());
        }
         
        int M = Integer.parseInt(sc.next());
        for(int i=1; i<=M; i++) {
            int vertex = Integer.parseInt(sc.next());
            int connectedVertex = Integer.parseInt(sc.next());
            adList.get(vertex).add(connectedVertex);
            // 자기 자신으로 들어오는 간선의 개수도 함께 체크
            indegree[connectedVertex]++;
        }
         
         
        // 우선 순위 큐 이용
        pq = new PriorityQueue<>();
        answer = new ArrayList<>();
        // 이 문제는 사이클이 존재하지 않게 데이터가 주어지므로 규칙 3번을 주의하여 구현
        topological_sort();
 
        // 정답 출력
        while(!answer.isEmpty()) {
            System.out.print(answer.remove(0) + " ");
        }
    }
    private static void topological_sort() {
        // indegree 간선의 개수가 0개인 정점을 큐에 넣는다.
        // 우선순위 큐이므로 낮은 번호의 정점이 우선시 됩니다.
        for(int i=1; i<=N; i++) {
            if(indegree[i] == 0) {
                pq.add(i);
            }
        }
         
        for(int i=1; i<=N; i++) {
            int curNode = pq.poll();
            // 정답 출력을 위해 위상정렬 순대로 저장
            answer.add(curNode);
            ArrayList<Integer> curNodeList = adList.get(curNode);
            // curNode와 연결된 모든 정점을 찾는다.
            while(!curNodeList.isEmpty()) {
                int target = curNodeList.remove(0);
                indegree[target]--;
 
                // indegree 개수가 '0'이 되면 queue에 넣는다.
                if(indegree[target] == 0) {
                    pq.add(target);
                }
            }
        }
         
    }
}