백준 - 2623번 음악프로그램 - java

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

접근법

기본적인 위상정렬문제로 쉽게 해결!
위상정렬의 핵심은 inDegree 배열. 각 인덱스별로 앞서 필요한 항목의 수 만큼 count를 가지고 있고, 조치가 취해지면 count를 깍아나가는 식으로 접근하면 됨
graph는 선행 -> 후행의 관계를 잡기위해 마련한 변수.

1. 입력에 따라 선행, 후행 관계를 graph 배열의 인덱스에 맞게 생성.
2. 생성하면서 후행이 되는 인덱스는 inDegree 배열 값도 올려줌
3. 초기에는 inDegree배열이 0인 값 = 선행조건이 없는 값을 Queue에 넣어주고 반복문

소스

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

public class Main {
	static int N; // 가수 수
	static int M; // 보조 PD 수
	static int[] inDegree; // 위상정렬 행렬
	static Node[] graph; // 링크관계를 담는 행렬
	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 Node[N+1];
		
		for(int i = 1; i < graph.length; i++) {
			graph[i] = new Node(i);
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int lineCnt = Integer.parseInt(st.nextToken());
			int[] tempArr = new int [lineCnt];
			for(int j = 0; j < lineCnt; j++) {
				tempArr[j] = Integer.parseInt(st.nextToken());
			}
			for(int j = 0; j < lineCnt-1; j++) {
				graph[tempArr[j]].link.add(tempArr[j+1]); //지금 인덱스의 graph에 다음 인덱스를 링크로 연결
				inDegree[tempArr[j+1]]++; //다음 인덱스는 값을 증가시킴
			}
		}		
		topologicalSort();
	}
	static void topologicalSort() {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		Queue<Integer> q = new LinkedList<Integer>();
		
		for(int i = 1; i < inDegree.length; i++) {
			if(inDegree[i] == 0) q.offer(i);
		}
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			answer.add(cur); // 출력 리스트에 넣어주고
			
			// 해당 노드에 연결된 항목들을 조사해서 inDegree깍아주고, 0이면 q에 offer
			for(int i = 0; i < graph[cur].link.size(); i++) {
				int link = graph[cur].link.get(i);
				inDegree[link]--;
				if(inDegree[link] == 0) q.offer(link);
			}			
		}
		
		if(answer.size() != N) {
			System.out.println("0");
			return;
		}
		for(int i = 0; i < answer.size(); i++) System.out.println(answer.get(i));
	}
}
class Node{
	int index;
	ArrayList<Integer> link;
	Node(int index){
		this.index = index;
		link = new ArrayList<Integer>();
	}
}