2623번 : 음악프로그램 [Java]

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

2623번: 음악프로그램

해결 방안

위상 정렬을 사용해 해결한다.

 

주의할 점 

1. PD별 담당하는 가수들을 입력받을 때, from을 저장해가면서 받자.

2. 인접행렬에 입력 전, 이미 받은 간선인지 확인하고 받자.

 

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M;
	static LinkedList<Integer>[] list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] map = new int[N + 1][N + 1];
		int[] indegree = new int[N + 1];

		for (int i = 0; i < M; i++) {
			int n = sc.nextInt();
			int from = sc.nextInt();
			for (int j = 1; j < n; j++) {
				int to = sc.nextInt();

				if (map[from][to] == 0) {
					map[from][to] = 1;
					indegree[to]++;
				}
				from = to;
			}
		}

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0)
				queue.add(i);
		}

		StringBuilder sb = new StringBuilder();
		while (!queue.isEmpty()) {
			int node = queue.poll();
			sb.append(node).append("\n");
			for (int i = 1; i <= N; i++) {
				if (map[node][i] == 1) {
					indegree[i]--;
					if (indegree[i] == 0)
						queue.add(i);
				}
			}
		}

		boolean flag = true;
		for (int i = 1; i <= N; i++) {
			if (indegree[i] != 0) {
				flag = false;
				break;
			}
		}

		if (flag)
			System.out.println(sb);
		else
			System.out.println(0);
	}
}