ALGORITHM/BOJ
[백준] 2623 음악프로그램
0298
2021. 2. 23. 16:46
2623번: 음악프로그램
첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한
www.acmicpc.net
2021-02-23
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main2623 {
public static List<List<Integer>> list;
public static Queue<Integer> q;
public static int[] arr;
public static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N+1];
q = new LinkedList<>();
list = new ArrayList<>();
for(int i = 1; i <= N+1; i++) list.add(new ArrayList<>());
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(st.nextToken());
int cur = Integer.parseInt(st.nextToken());
while(st.hasMoreTokens()) {
int next = Integer.parseInt(st.nextToken());
list.get(cur).add(next);
arr[next]++;
cur = next;
}
}
// 1. 진입 차수가 0이면 queue에 넣는다.
for(int i = 1; i <= N; i++) {
if(arr[i] == 0) q.add(i);
}
StringBuilder sb = new StringBuilder();
int count = 0;
while(!q.isEmpty()) {
int idx = q.poll();
sb.append(idx).append("\n");
count++;
// 2. queue에서 꺼내서 연결된 순서들을 체크한다.
for(int i = 0; i < list.get(idx).size(); i++) {
int num = list.get(idx).get(i);
//3. 연결된 순서들의 진입차수를 하나씩 제거해가면서, 새롭게 진입차수가 0이되면 queue에 넣는다.
if(--arr[num] == 0) q.add(num);
}
}
if(count != N) System.out.println("0");
System.out.println(sb.toString());
}
}
|
cs |
#문제풀이
위상정렬 문제이다.
주석에 푼 순서를 적어놓았다.