백준 1766번 : 문제집 [자바]

🧫 문제 분석

 

✔️ 출처

문제집 골드 2

 

📖 문제

 

위상정렬 + 우선순위 큐 문제

 

먼저 푸는게 좋은 문제들은 

위상정렬로 진입차수를 저장해준다.

 

a b 로 a가 먼저 푸는게 좋은 문제면

b의 진입차수 1을 늘려준다.

 

그리고 진입차수가 0인 문제들을 전부 우선순위 큐에 저장하고

 

하나씩 꺼내서 문제를 푼다. (우선순위 큐 기본 정렬을 사용했으므로 오름차순 정렬되어 난이도가 낮은 순으로 나온다.)

풀고 해당 문제가 먼저 푸는게 좋은 문제였다면 

연결되어있는 뒤 문제들의 진입차수를 -1 해준다. 

 

이때 연결된 문제들의 진입차수가 0이 되었다면 더이상 먼저 푸는게 좋은 문제는 존재하지 않으므로

해당 문제도 우선순위 큐에 저장한다. 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Integer>[] graph = new List[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        int[] topology = 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());

            graph[a].add(b);
            topology[b]++; // 진입차수 증가
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        // 진입차수가 0인 먼저 풀거나, 그냥 풀어도되는 문제들 저장
        for (int i = 1; i <= N; i++) {
            if (topology[i] == 0) {
                pq.add(i);
            }
        }

        // 쉬운 문제들 부터 꺼내서 풀이
        while (!pq.isEmpty()) {
            int num = pq.poll();
            sb.append(num).append(" ");
            // 현재 푼 문제가 먼저 풀어야 좋은 문제였으면 풀렸음을 표시한다. 
            for (int problem : graph[num]) {
                topology[problem]--; 

                // 먼저 풀어야 좋은 문제가 더이상 없다면 해당 문제도 우선순위큐에 삽입
                if (topology[problem] == 0) {
                    pq.add(problem);
                }
            }
        }


        System.out.println(sb.toString());
    }



}

 

 

 

❗ 오답노트 / 필요한 지식

1.