BOJ 2623 음악프로그램 [Java]

BOJ 2623 음악프로그램

1. 문제 링크

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

2. 문제 해설

pd들이 정한 조건에 따라 가수 순서가 정해지고 그에 맞춰 정렬을 해줘야하는 문제이다. 위상정렬이 떠올랐다.
위상정렬에 대해 알고 싶다면 아래의 글을 참고해보자.

위상 정렬(Topological sorting) [Java]

문제에서 주어진 예시를 아래 그림으로 한번 나타내보았다.

사이클이 있으면 위상정렬을 할 수가 없는데, 문제에서 세번째 pd가 정해준 순서 2->3이 3->2로 바뀐다고 했을 때 불가능하다고 한 이유가 사이클이 생기기 때문이다.
코드에 대한 설명을 해보자면, indeg 배열은 각 정점들에 들어오는 간선의 수를 담은 배열이고, arr에 인접리스트 방식으로 그래프를 나타냈다.
26~37줄까지의 코드에서 주어지는 입력 값을 받으면서 arr와 indeg를 채워준다.
그 후에는 아래의 과정을 거쳐서 위상정렬을 해준다.

1. indeg 배열을 돌면서 indeg가 0인 정점을 큐에 담는다.
2. 큐의 맨 앞에 있는 정점을 빼고, 위상정렬 결과에 담는다.
3. 해당 정점과 연결되있는 모든 정점의 indeg 값을 -1 해준다. -1 해준 indeg 값이 0이 되면 그 정점도 큐에 담는다.
4. 총 정점의 수 만큼 2, 3과정을 반복해주고, 만약 중간에 큐가 빈다면 사이클이 존재한다는 의미이다.

위에서 사이클이 있으면 위상정렬을 할 수 없고, 위상정렬 과정 중 큐가 빈다면 사이클이 존재한다는 의미라고 했는데 왜 그런 것인지 알아보자.
위 과정에서는 indeg가 0인 정점을 큐에 넣어준다. 그런데 만약 사이클이 존재한다면 사이클에 속한 정점들은 indeg가 0이 될 수가 없다.
그렇기 때문에 총 정점의 수만큼 반복하는 동안 indeg가 0이 아닌 정점이 발생할 수 밖에 없고 큐에 넣어줄 정점이 없게되는 순간이 무조건 온다.
그렇기에 위상정렬을 진행하는 동안 큐가 비게 되면 사이클이 존재한다는 의미이다.

3. 코드 보기

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[] indeg;
    static ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
    static StringBuilder sb = new StringBuilder();

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        indeg=new int[n];

        for (int i = 0; i < n; i++) {
            arr.add(new ArrayList<>());
        }

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

            for (int j = 0; j < num - 1; j++) {
                int nxt = Integer.parseInt(st.nextToken());
                arr.get(cur - 1).add(nxt - 1);
                indeg[nxt-1]++;
                cur = nxt;
            }
        }

        topoSort();

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    static void topoSort() {
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.add(i);
            }
        }

        for (int i = 0; i < n; i++) {
            if (q.isEmpty()) {
                System.out.println(0);
                System.exit(0);
            }

            int cur = q.poll();
            sb.append(cur + 1 + "\n");

            for (int child : arr.get(cur)) {
                indeg[child]--;

                if (indeg[child] == 0) {
                    q.add(child);
                }
            }
        }
    }
}