[백준] 음악프로그램 2623 - java

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

2623번: 음악프로그램

public class Main {
	
	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());
		
		int inDegree[] = new int[N+1];
		boolean visited[] = new boolean[N+1];
		int adj[][] = new int[N+1][N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int len = Integer.parseInt(st.nextToken());
			int from = Integer.parseInt(st.nextToken());
			for(int j=0; j<len-1; j++) {
				int to = Integer.parseInt(st.nextToken());
				adj[from][to] = 1;
				from = to;
			}
		}
		
		Queue<Integer> q = new LinkedList<Integer>();
		countInDegree(adj, inDegree);
		pushQueue(q, visited, inDegree);
		
		int result[] = new int[N];
		int resultIdx = 0;
		while(!q.isEmpty()) {
			result[resultIdx] = q.poll();
			removeInDegree(result[resultIdx], adj, inDegree);
			pushQueue(q, visited, inDegree);
			resultIdx++;
		}
		
		if(resultIdx != N) {
			System.out.println(0);
		}
		else {
			for(int i=0; i<resultIdx; i++) {
				System.out.println(result[i]);
			}
		}
	}

	private static void removeInDegree(int cur, int[][] adj, int[] inDegree) {
		for(int i=1; i<=N; i++) {
			if(adj[cur][i] == 1) {
				inDegree[i]--;
			}
		}
	}

	private static void pushQueue(Queue<Integer> q, boolean[] visited, int[] inDegree) {
		for(int i= 1; i<=N; i++) {
			if(inDegree[i] == 0 && !visited[i]) {
				q.offer(i);
				visited[i] = true;
			}
		}
	}
	
	private static void countInDegree(int[][] adj, int[] inDegree) {
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(adj[i][j] == 1) {
					inDegree[j]++;
				}
			}
		}
	}
}

위상정렬 문제였습니다.

위상정렬은 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어질 때 입니다.

 

1. adj에 간선을 입력 받습니다.

2. 진입 차수가 0인 정점들을 q에 넣습니다.

3. q에서 값을 빼고 그 값과 연결된 간선인 정점들의 진입 차수들을 갱신합니다.

4. 진입 차수가 0이 되면 q에 넣습니다.

3~4를 반복하고 결과를 모두 구하기전에 q가 비게 되면 위상정렬이 불가능하므로 0을 출력합니다.