[백준] 2623. 음악프로그램 (Java)

 

🔒 문제

2623번: 음악프로그램

 

🔑 알고리즘

위상 정렬

 

 

💡  풀이

보조 PD마다 생각한 가수의 순서가 정해져있으므로 위상정렬을 이용한다.

 

각 순서가 제시한 순서를 탐색하며 첫번째가 아닌 가수들의 번호의 진입차수를 1씩 늘린다.

또 앞의 원소와 뒤의 원소를 그래프로 연결한다.

예를 들어, 1 4 3 이라는 순서가 있다면 1->4 , 4->3을 그래프로 연결한다.

for (int j = 1; j < num; j++) {
	int after = Integer.parseInt(st.nextToken());
		
	graph[before].add(after); // 그래프 연결
	InDegree[after]++;        // 진입 차수 증가
	before = after;
}

 

입력이 끝난 후 진입 차수가 0인 가수들을 출력에 저장하고 큐에 삽입하고,

Queue<Integer> queue = new LinkedList<>();
for(int i=1; i<=N; i++) {
	if(InDegree[i] == 0) {
		queue.add(i);
		sb.append(i).append("\n");
	}
}

 

위상 정렬을 수행하며 진입 차수가 0이 된 원소들을 출력에 저장한다.

while(!queue.isEmpty()) {
	int cur = queue.poll();
			
	for(int target: graph[cur]) {
		if(--InDegree[target] == 0) {
			queue.add(target);
			sb.append(target).append("\n");
		}
	}
}

 

 

위상 정렬의 수행이 끝나면

전체 진입 차수 리스트를 확인하고 진입 차수가 모두 0이라면 저장한 결과를 출력하고

진입 차수가 0이 아닌 원소가 있다면 사이클이 있는, 가수의 출연 순서를 정할 수 없는 경우이므로 0을 출력한다.

 

// 사이클 확인
for(int i=1; i<=N; i++) {
	if(InDegree[i] != 0) {
		System.out.println(0);
		System.exit(0);
	}
}

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] InDegree = new int[N + 1];

		ArrayList<Integer>[] graph = new ArrayList[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 after = Integer.parseInt(st.nextToken());
				
				graph[before].add(after); // 그래프 연결
				InDegree[after]++;        // 진입 차수 증가
				before = after;
			}
		}
		
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1; i<=N; i++) {
			if(InDegree[i] == 0) {
				queue.add(i);
				sb.append(i).append("\n");
			}
		}
		
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			
			for(int target: graph[cur]) {
				if(--InDegree[target] == 0) {
					queue.add(target);
					sb.append(target).append("\n");
				}
			}
		}

		// 사이클 확인
		for(int i=1; i<=N; i++) {
			if(InDegree[i] != 0) {
				System.out.println(0);
				System.exit(0);
			}
		}
		
		System.out.println(sb);
	}
}