[백준 2623] 음악프로그램 / 자바 / 위상정렬

#문제         

레벨: G3
알고리즘: 위상정렬 
풀이시간:  1시간
힌트 참조 유무: 유

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

 

---

#문제 풀이        

위상정렬이란 순서가 정혀져 있는 작업을 순서를 정해주는 작업을 뜻한다.

코드는 큐로 구현된다. 방향성이 있는 선들을 하나 씩 끊어주는 느낌으로 구현하면된다. 그리고 선이 다 끊어진 노드들은 결과에 포함시킨다. 글보다는 코드로 보는 것이 이해가 더 쉬울  것이다. 아래를 참조바란다.

---

#풀이 코드      

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

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] inDegree;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        inDegree = new int[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 count = Integer.parseInt(st.nextToken());
            int prev = Integer.parseInt(st.nextToken());
            for (int j = 1; j < count; j++) {
                int curr = Integer.parseInt(st.nextToken());
                graph[prev].add(curr); //자식 관계 저장
                inDegree[curr]++; // 부모노드가 자식 노드 방문할 수 있는 경우의 수 +1
                prev = curr;
            }
        }

        ArrayList<Integer> result = topologicalSort();

        if (result.size() == N) {
            for (int singer : result) {
                System.out.println(singer);
            }
        } else {
            System.out.println(0);
        }
    }

    static ArrayList<Integer> topologicalSort() {
        ArrayList<Integer> result = new ArrayList<>(); 
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {    // 맨 앞 순서 노드를 뜻함
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);  // 큐에서 꺼내면 결과에 추가

            for (int next : graph[current]) { // 자식 노드들 탐색
                inDegree[next]--;   // 부모노드에서 한 번 방문 했으므로 -1
                if (inDegree[next] == 0) { // 모든 부모노드를 방문했했으면 큐에 집어넣기
                    queue.offer(next);
                }
            }
        }

        return result;
    }
}