백준 2632번 : 음악프로그램 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

음악프로그램 골드 3

 

📖 문제

 

위상정렬 문제로 간단하게 위상정렬 풀이를 하면된다.

진입차수가 0인 것만 BFS 탐색을 해주고 

 

중복 탐색을 하지 않게 처리만 잘 해주면 간단한 문제다.

 

---

🔅 문제 풀이

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int[] indegree;
    static List<Integer>[] graph;
    static boolean[] visited;
    static int orderCount = 0;

    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());

        indegree = new int[n + 1];
        graph = new List[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());

            int pre = Integer.parseInt(st.nextToken());

            // cnt 개의 노드가 주어진 순서대로 연결되므로 간선과 진입 차수 설정
            for (int j = 1; j < cnt; j++) {
                int next = Integer.parseInt(st.nextToken());
                graph[pre].add(next);

                // 위상정렬
                indegree[next]++;
                pre = next;
            }

        }

        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0 && !visited[i]) {
                bfs(i);
            }
        }

        System.out.print(orderCount < n ? 0 : sb.toString());

    }

    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        while (!q.isEmpty()) {
            int current = q.poll();
            visited[current] = true;

            sb.append(current).append("\n");
            orderCount++;

            List<Integer> list = graph[current];
            for (int next : list) {
                indegree[next]--; // current에서 next로 가는 간선을 제거하므로 next의 진입 차수 감소

                if (indegree[next] == 0) {
                    q.add(next);
                }
            }
        }
    }


}

 

 

 

❗ 오답노트 / 필요한 지식

1.  중복 체크는 그래프에서 필수다.