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

1. 문제

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

2623번: 음악프로그램

 

 

 

2. 풀이 과정

1. 순서 찾기 : 위상정렬

2. 정렬이 안 되는 경우는 자신 앞에 있는 노드 수가 0이상인 노드만 남았을 때이다. 이 경우, 사이클이기 때문에 주어진 조건을 모두 만족하는 순서를 찾을 수 없다.

 

import java.io.*;
import java.util.*;

public class boj2623 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());//가수 수
		int M = Integer.parseInt(st.nextToken());//PD수
		LinkedList<Integer> back[] = new LinkedList[N+1];
		int front[] = new int[N+1];
		
		//init
		for(int i=1; i<=N; i++) {
			back[i] = new LinkedList<>();
		}
		
		//data setting
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken()), e;
			for(int j=1; j<cnt; j++) {
				e = Integer.parseInt(st.nextToken());
				back[s].add(e);
				front[e]++;
				s = e;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		Queue<Integer> q = new LinkedList<>();
		for(int i=1; i<=N; i++) {
			if(front[i]==0) {
				q.add(i);
			}
		}
		
		//algorithm
		int result = N;
		while(!q.isEmpty()) {
			int su = q.poll();
			result--;
			sb.append(su+"\n");
			for(int next : back[su]) {
				if(--front[next]==0) {
					q.add(next);
				}
			}
		}
		
		//result
		System.out.println((result > 0) ? "0" : sb.toString());
	}

}

 

결과