[Java] 백준 BOJ / 2623번: 음악프로그램

음악프로그램

문제

---

문제 설명

간단하게 설명하자면 메인 PD가 되어서 보조 PD들의 요구를 모두 맞춰주어야 하는 문제이다.

문제 예제를 예를 들어 설명하면 6팀의 가수가 있다고 했을 때 보조 PD들이 아래와 같이 순서를 정해왔다고 하자.

1 4 3
6 2 5 4
2 3

보조PD들이 정해온 순서를 모두 만족시키기 위해서는 6 -> 2 -> 1 -> 5 -> 4 -> 3 이런 식으로 순서를 정한다면 모든 조건을 만족 시킬 수 있다.

이렇게 보조 PD들의 요구를 모두 만족시키는 순서를 찾는 프로그램을 작성하면 된다.

---

구현

이 문제는 위상정렬로 접근해야 한다.

문제에서는 특정한 순서를 지켜야 한다 라는 조건이 있고, 전체 순서를 출력해야 하며 사이클을 판별을 해야하기 때문에 전형적인 위상 정렬 문제이다.

일단 입력을 받아보자. 필요한 자료구조는 진입차수를 판단하기 위한 n + 1 짜리 indegree 배열과, 보조 PD 들이 정한 순서를 기반으로 각 팀 별로 어떤 팀이 뒤로 올지를 저장할 ArrayList 배열이 필요하다.

indegree = new int[n + 1];
graph = new List[n + 1];

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

이렇게 선언한 graph 에 PD들이 정한 순서를 넣어줘야 한다.

for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
    int num = Integer.parseInt(st.nextToken());
	int before = Integer.parseInt(st.nextToken());
	for (int j = 1; j < num; j++) {
		int cur = Integer.parseInt(st.nextToken());
		graph[before].add(cur);
        indegree[cur]++;
		before = cur;
	}
}

위와 같이 몇명 들어오는지 num을 입력을 받고 나서 맨 처음 팀을 before에 저장을 한다.
그 후에는 순서대로 before의 ArrayList에 다음에 오는 팀인 cur 을 넣어주고, 그 cur 의 진입차수를 하나씩 증가시키면 된다.

그리고 이제 위상정렬을 구현하기 위해 Queue를 선언해주고 초기화 해준다.

indegree 가 0이라면 우선순위가 가장 높다는 것이기 때문에 모두 Queue에 넣어주고 시작한다.

queue = new LinkedList<>();

for (int i = 1; i <= n; i++) {
	if(indegree[i] == 0)
		queue.offer(i);
}

그리고 위상정렬을 구현을 한다.

일단 queue에 들어왔다는 것은 진입차수가 0이므로, 바로 빠져도 된다는 뜻이니 가장 위에있는 값을 poll 해주고, 해당 값을 출력한다.

그리고 이번 문제에서 사이클을 판단해야하기 때문에 개수를 세준다.

그 후에 뽑은 curr 값 뒤의 값에 대해 진입차수를 한 개 감소 시키고 indegree 가 0이 되었다면 해당 next 값을 queue 에 넣어주고 출력을 해주면 된다.

---

코드

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

public class Main_2623_topologicalSort {
    static int n, m;
    static List<Integer>[] graph;
    static int[] indegree;
    static Queue<Integer> queue;
    static StringBuilder sb = new StringBuilder();
    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());

        indegree = new int[n + 1];
        graph = new List[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 num = Integer.parseInt(st.nextToken());
            int before = Integer.parseInt(st.nextToken());
            for (int j = 1; j < num; j++) {
                int cur = Integer.parseInt(st.nextToken());
                graph[before].add(cur);
                indegree[cur]++;
                before = cur;
            }
        }

        queue = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            if(indegree[i] == 0)
                queue.offer(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            sb.append(curr).append("\n");
            count++;

            for (int next : graph[curr]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        System.out.println(count == n ? sb : 0);
    }
}