[2623] 음악프로그램 - Java[자바]

 

| 문제 링크

 

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

2623번: 음악프로그램

 

 

 

 

---

 

 

 

 

| 문제

 

1. N명의 가수와 M명의 보조 PD가 주어집니다.
2. 보조 PD별로 계획한 가수들의 출연 순서를 고려해 가능한 출연 순서를 출력하시오.
   출연 순서를 정할 수 없는 경우 0을 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 위상정렬 문제로 각 가수별 인접리스트(graph), 이전에 등장해야하는 가수의 수를 표현한 배열(degree) 를 구현합니다.
2. 가수별로 사이클이 존재하는 경우 순서를 출력할 수 없어, 위상정렬을 하면서 노드의 개수를 카운트 해줍니다.
3. 만약 카운트 횟수가 노드의 총 수(가수들의 수, N)와 다르다면 사이클이 존재하는 것으로 간주

 

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int M;
	public static int cnt;
	public static int[] degree;
	public static List<Integer>[] graph;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		//노드에 연결된 정보를 보기위한 List 배열 초기화
		graph = new ArrayList[N+1];
		degree = new int[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());
			st.nextToken();
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			graph[a].add(b);
			degree[b]++;
			
			while(st.hasMoreTokens()) {
				a=b;
				b = Integer.parseInt(st.nextToken());
				graph[a].add(b);
				degree[b]++;
			}
		}
        	//위상 정렬
		topologic();
        	//만약 위상 정렬시 카운트된 노드의 개수가 N과 같지 않다면 사이클이 존재하는 것으로 간주
		if(cnt==N) {
			bw.write(sb.toString());
		}
		else
			bw.write("0");
		br.close();
		bw.close();
		
	}
	
	public static void topologic() {
		Queue<Integer> que = new LinkedList<>();
        	//사전 노드가 없는 노드를 정렬의 시작으로 설정
		for(int i = 1; i<=N; i++) {
			if(degree[i]==0)
				que.add(i);
		}
		
		while(!que.isEmpty()) {
			cnt++;
			int node = que.poll();
			sb.append(node).append('\n');
			for(int i : graph[node]) {
            		//이전 노드들이 모두 나온경우 다음 노드로 넘어갈 수 있음
				if(--degree[i]==0)
					que.add(i);
			}
		}
	}

}