백준 2623번 : 음악프로그램 (Java)

 문제

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

2623번: 음악프로그램

2623 음악프로그램

 

 구현 방법

출연 순서가 정해져 앞 가수가 먼저 출연해야 다음 가수가 출연할 수 있으므로 위상 정렬 알고리즘을 사용했습니다.

 

입력이 여러 가지로 나뉘어 들어오지만 결국 하나의 그래프임을 알 수 있습니다.

각 보조 PD가 담당하는 순서 관계를 전부 저장한 뒤 위상 정렬을 돌리면 끝~.~

 

위상 정렬을 단계별로 나열하면

1. 가수들의 진입 차수를 확인하여 0인 가수만 큐에 삽입 (가수 번호 저장) 

2. 큐에 삽입한 가수들을 하나씩 빼내어 이동할 수 있는 정점 확인

3. 이동할 수 있는 정점의 진입 차수가 0이면 큐에 삽입

4. 2-3 반복하다 순서를 확정지은 가수의 수가 전체 가수의 수와 같다면 true 출력

5. 만약 큐가 빈 값이 될 때까지 모든 가수의 순서를 정하지 못했다면 false 출력

6-1. 출연 순서가 모두 정해지면 저장해놓았던 가수 번호 출력

6-2. 출연 순서가 모두 정해지지 않았다면 0 출력

 

 구현 코드

package BOJ.Gold;

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

public class B2623_음악프로그램 {
	static int N, M, inDegree[], cnt;
	static List<List<Integer>> list = new ArrayList<>();
	static Queue<Integer> queue = new LinkedList<>();
	static StringBuilder sb = new StringBuilder();
	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];
		for (int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
		}
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int size = Integer.parseInt(st.nextToken()); // 보조 PD가 담당하는 가수 수
			int from = Integer.parseInt(st.nextToken()); 
			for (int j=1;j<size;j++) {
				int to = Integer.parseInt(st.nextToken());
				list.get(from).add(to); // 간선 저장
				inDegree[to]++; // 진입 차수 저장
				from = to; // 현재 뒷 순서가 다음의 앞 순서
			}
		}
		if (topology()) System.out.println(sb);
		else System.out.println(0);
	}
	
	static boolean topology() {
		for (int i=1;i<=N;i++) {
			if (inDegree[i] == 0) { // 진입 차수가 0이면 진입 가능
				queue.offer(i);
				sb.append(i+"\n"); // 순서 저장
				cnt++;
			}
		}
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			for (int next : list.get(now)) { // 이동할 수 있는 정점 중
				if (--inDegree[next] == 0) { // 진입 차수가 0이면 진입 가능
					queue.offer(next);
					sb.append(next+"\n");
					// 모든 가수들의 순서를 정하면 true 리턴
					if (++cnt == N) return true;
				}
			}
		}
		// 순서를 정하는 것이 불가능하면 false
		return false;
	}
}

 

정답!