백준 2623 음악프로그램 [자바]

16 Jun 2022 in Develop / Solving

java

문제 분석

• 여러 PD가 출연자의 순서를 정해온다.
• PD들이 발한 순서를 모두 만족하도록, 전체 가수의 순서를 정하여라.
• 순서를 정하는 것이 불가능 할 때는 0 출력.

입력조건

가수의 수 N 피디의 수 M
M줄에 걸쳐 {
	피디가 담당한 가수의 수 A , 가수의 순서 나열
}

풀이과정

• 위상정렬.
• 위상정렬을 할 때는, 2차원 배열로 그래프를 그리고 계산하는 것이 일반적이지만, 여기에서는 리스트에 간선을 저장하고, 진입차수를 따로 저장하여 처리하였다.

코드 구성

• 그래프 저장

  int[] indegree = new int[N+1];
  ArrayList<Integer>[] grp = new ArrayList[N+1];
  for(int i = 1; i <= N; i++) grp[i] = new ArrayList<>();
    
  for(int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      if(a == 0) continue;
    
      int f = Integer.parseInt(st.nextToken());
      for(int j = 0; j < a-1; j++) {
          int b = Integer.parseInt(st.nextToken());
          indegree[b]++;
          tot++;
          grp[f].add(b);
          f = b;
      }
  }
  

• 위상정렬

  Queue<Integer> que = new LinkedList<Integer>();
  for(int i = 1; i <= N; i++)
      if(indegree[i] == 0) que.add(i);
    
  StringBuilder ans = new StringBuilder();
  while(!que.isEmpty()) {
      int now = que.poll();
      ans.append(now + "\n");
    
      for(int num : grp[now]) {
          indegree[num]--;
          tot--;
          if(indegree[num] == 0)
              que.add(num);
      }
  }
  

전체 코드

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 BJ2623_음악프로그램 {
	public static void main(String[] args) throws IOException {
		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());
		
		int tot = 0;
		int[] indegree = new int[N+1];
		ArrayList<Integer>[] grp = new ArrayList[N+1];
		for(int i = 1; i <= N; i++) grp[i] = new ArrayList<>();
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			if(a == 0) continue;
			
			int f = Integer.parseInt(st.nextToken());
			for(int j = 0; j < a-1; j++) {
				int b = Integer.parseInt(st.nextToken());
				indegree[b]++;
				tot++;
				grp[f].add(b);
				f = b;
			}
		}
		// 그래프 생성 완료.
		
		// 디버그
//		System.out.println(Arrays.toString(indegree) + " " + tot);
//		for(int i = 1; i <= N; i++) {
//			System.out.println(grp[i].toString());
//		}
		
		Queue<Integer> que = new LinkedList<Integer>();
		for(int i = 1; i <= N; i++)
			if(indegree[i] == 0) que.add(i);
		
		StringBuilder ans = new StringBuilder();
		while(!que.isEmpty()) {
			int now = que.poll();
			ans.append(now + "\n");
			
			for(int num : grp[now]) {
				indegree[num]--;
				tot--;
				if(indegree[num] == 0)
					que.add(num);
			}
		}
		
		if(tot != 0) System.out.print(0);
		else System.out.println(ans);
		
	}
}