BOJ - 음악프로그램

2623 음악프로그램 : https://www.acmicpc.net/problem/2623

---

Problem

---

Solve

순서를 정해야하는데, 순위에 먼저 수행해야하는 우선순위가 있다면, 위상정렬을 고려해보아야합니다.

위상정렬에서 먼저 수행되어야할 것의 여부를 알기 위해서는 indegree를 이용합니다.
indegree[i]가 0이라면 우선적으로 수행해야하는 것이 없으며, 0이 아니라면 우선적으로 수행해야하는 값이 있다는 뜻입니다.

Queue를 이용해서 모든 값들을 탐색해볼것입니다.
먼저 indegree가 0인 값을 찾아 queue에 저장해주고 차례로 queue에 저장된 값과 연결된 값들의 indegree를 하나씩 감소시킵니다. indegree[i]를 감소시킴으로써 queue에서 나온 값이 i보다 먼저 수행되었기 때문에 i의 우선순위 값 수를 줄여주기 위함입니다.

그리고 해당 문제에서 모든 가수의 순서가 수행되는지 여부를 판단해야합니다.
저는 처음에 각 PD들이 담당할 가수를 통해 indegree를 초기화해줄때 indegree의 값들을 모두 누적해주었습니다.(indegreeCount)
그리고 위상정렬에서 다음 가수를 탐색하였을때 indegree누적값을 하나씩 감소시킴으로써, 위상정렬이 끝났을때 indegree누적값이 0이라면 모든 가수의 순서가 수행되었고, 아니라면 수행되지 않음으로 판단하였습니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
public class Main{
	static int[] indegree;
	static List<Integer>[] edges;
	static int indegreeCount;
	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()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		indegreeCount = 0;
		indegree = new int[N+1];
		edges = new List[N+1];
		for(int i=1;i<=N;i++){
			edges[i] = new ArrayList<>();
		}

		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine()," ");
			int n = Integer.parseInt(st.nextToken());

			if(n==0) continue;

			int prevSinger = Integer.parseInt(st.nextToken());
			for(int j=1;j<n;j++){
				int singer = Integer.parseInt(st.nextToken());

				indegree[singer]++;
				edges[prevSinger].add(singer);
				prevSinger = singer;
				indegreeCount++;
			}
		}

		Queue<Integer> sequence = topologicalSort();

		StringBuilder sb = new StringBuilder();
		if(!isValid()){
			sb.append("0");
		}else{
			while(!sequence.isEmpty()){
				sb.append(sequence.poll()).append("\n");
			}
		}

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

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

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

		while(!queue.isEmpty()){
			int current = queue.poll();

			result.offer(current);
			for(int link : edges[current]){
				if(--indegree[link] == 0) queue.offer(link);
				indegreeCount--;
			}
		}

		return result;
	}

	static boolean isValid(){
		return indegreeCount == 0;
	}
}

---

Result

---

Reference