Java/백준
[Java][2623] 음악프로그램
tmd1
2023. 2. 15. 18:35
문제:
https://www.acmicpc.net/problem/2623
2623번: 음악프로그램
첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한
www.acmicpc.net
코드:
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
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());
// 인접 리스트 , 초기화
ArrayList<ArrayList<Integer>> arr = new ArrayList<>(n+5);
for(int i=1;i<=n+3;i++){
arr.add(new ArrayList<>());
}
// 자신을 향하는 화살표 개수
int [] indegree = new int[32005];
while(m-->0){
String s = br.readLine();
String [] split = s.split(" ");
// 인접리스트에 저장(split[i]는 split[i+1]을 가리킴)
// split[i+1]은 가리킴을 받으므로 indegree[split[i+1]]을 1씩 증가
for(int i=1;i< split.length-1;i++){
arr.get(Integer.parseInt(split[i])).add(Integer.parseInt(split[i+1]));
indegree[Integer.parseInt(split[i+1])]++;
}
}
// 위상정렬
Queue<Integer> q = new LinkedList<>();
for(int i=1;i<=n;i++){
// 가리킴 받는 것이 없으면 q에 추가
if(indegree[i] == 0) q.add(i);
}
// 결과 배열
ArrayList<Integer> result = new ArrayList<>();
while(!q.isEmpty()){
// q에서 뽑아냄
int cur = q.poll();
// 결과 배열에 추가
result.add(cur);
// 뽑아낸 수를 그래프에서 제거
// 뽑아낸 수가 가리킨 수의 indegree가 1씩 감소함
// 감소해서 자신을 가리킨 화살표가 없다면 q에 추가
for(int nxt : arr.get(cur)){
indegree[nxt]--;
if(indegree[nxt] == 0) q.add(nxt);
}
}
// result 사이즈가 n과 다르다면 위상정렬이 불가능 (사이클)
if(result.size() != n){
System.out.println(0);
}else{
for(int i=0;i<result.size();i++)
System.out.println(result.get(i));
}
}
}
위상정렬
참고: