[백준] 1766번 문제집

문제 설명

• https://www.acmicpc.net/problem/1766
• Gold 2
• 풀이시간 : 10분

문제 풀이

• 위상 정렬을 조금 변형한 문제이다.
• 위상 정렬에 사용할 큐를 문제 번호 기준 오름차순 정렬하는 우선순위 큐를 사용한다.
• 풀이 순서는 아래와 같다.

  • 진입 차수가 0인 노드를 모두 우선순위 큐에 넣어준다.
  • 큐에서 빼면서(현재 풀 수 있는 가장 낮은 번호 문제) 출력해준다.
  • 해당 노드에 연결된 모든 노드의 진입 차수를 낮추고 진입 차수가 0인 노드 큐에 넣는다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N, M;
    static int[] inDegree;
    static List<List<Integer>> map;

    static void solve() throws IOException {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0)
                pq.add(i);
        }

        while(!pq.isEmpty()) {
            Integer cur = pq.poll();
            bw.write(cur + " ");

            for (int i = 0; i < map.get(cur).size(); i++) {
                int next = map.get(cur).get(i);
                if (--inDegree[next] == 0)
                    pq.add(next);
            }
        }
        bw.flush();
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //초기화
        inDegree = new int[N+1];
        map = new ArrayList<>();
        for (int i = 0; i <= N; i++) map.add(new ArrayList<>());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            inDegree[to]++;
            map.get(from).add(to);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * 문제집 (21:20)
 * N : 문제수
 * M : 먼저 푸는 것이 좋은 문제 정보 수
 *
 * - 위상 정렬 변형
 * - PQ를 이용한 위상 정렬
 * - PQ : 문제 번호에 따른 정렬
 *
 * N M
 * a b
 */