Link | 백준 2623번 문제 : 음악프로그램
특정 가수의 순서가 오려면 이전 가수들의 순서가 선행되어야 한다.
Graph 입장에서 보면 node의 탐색에 선행 node 탐색이 필요하다.
그렇기 때문에 위상정렬을 통해 해결할 수 있다.
Step 1. 진입차수와 진출 node를 저장하는 자료구조를 초기화한다.
int singerNum = Integer.parseInt(tokenizer.nextToken());
int pdNum = Integer.parseInt(tokenizer.nextToken());
int[] preSingerNum = new int[singerNum + 1];
Map<Integer, Set<Integer>> nextSingers = IntStream.rangeClosed(1, singerNum).boxed()
.collect(Collectors.toMap(n -> n, n -> new HashSet<>()));
preSingerNum[n]은 n번 가수보다 선행되어야 할 가술들의 수이다.
nextSingers.get(n)은 n번 가수 이후에 오는 가술들이다.
이 때 Set가 아닌 List으로 하면 중복이 될 수 있기 때문에 Set으로 선언한다.
Step 2. PD들이 원하는 가수들의 순서를 입력한다.
while (pdNum-- > 0) {
tokenizer = new StringTokenizer(reader.readLine());
int sortedSingerNum = Integer.parseInt(tokenizer.nextToken());
int preSinger = Integer.parseInt(tokenizer.nextToken()), postSinger;
while (sortedSingerNum-- > 1) {
postSinger = Integer.parseInt(tokenizer.nextToken());
if (nextSingers.get(preSinger).add(preSinger = postSinger)) preSingerNum[postSinger]++;
}
}
sortedSingerNum은 PD가 원하는 정렬 방법의 가수 수이다.
preSinger은 선행되는 가수이다. postSinger은 후행되는 가수이다.
nextSingers.get(preSinger).add(postSinger)을 통해 선행 가수의 후행 목록을 추가한다.
이 때 만약 true가 돌아온다면 처음 들어오는 조건이므로 후행 가수의 선행 가수 수를 추가한다.
추가로 preSinger = postSinger을 통해 선행 가수를 업데이트한다.
Step 3. 가수 정렬 목록과 선행 가수가 없는 가수들을 탐색한다.
List<Integer> singers = new ArrayList<>();
Queue<Integer> prepared = IntStream.rangeClosed(1, singerNum)
.filter(n -> preSingerNum[n] == 0).boxed()
.collect(Collectors.toCollection(LinkedList::new));
singers list는 가수들의 출연 순서이다.
prepared는 현재 선행 가수가 이미 출연한 가수들이다.
Step 4. 차례대로 탐색하면서 출연 순서를 결정한다.
while (!prepared.isEmpty()) {
int node = prepared.poll();
singers.add(node);
nextSingers.get(node).stream()
.peek(n -> preSingerNum[n]--)
.filter(n -> preSingerNum[n] == 0)
.forEach(prepared::offer);
}
prepared는 출연 가능한 가수 목록이기 때문에 나오는대로 바로 출연시킨다.
출연한 가수의 후행 가수들을 차례대로 탐색한다.
후행 가수의 선행 가수 수를 우선 1 감산한다.
만약 선행 가수 수가 0이 되면 후행 가수는 출연 대기 목록에 들어간다.
출연 대기자가 없을 때까지 반복한다.
Step 5. 출연 순서를 출력한다.
result.append(singers.size() == singerNum ?
singers.stream().map(String::valueOf).collect(Collectors.joining(" ")) : 0);
만약 출연자 수와 가수의 수가 다르다면 0을 출력한다.
같다면 출연자들의 출연 순서를 출력한다.
public void solve() throws IOException {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int singerNum = Integer.parseInt(tokenizer.nextToken());
int pdNum = Integer.parseInt(tokenizer.nextToken());
int[] preSingerNum = new int[singerNum + 1];
Map<Integer, Set<Integer>> nextSingers = IntStream.rangeClosed(1, singerNum).boxed()
.collect(Collectors.toMap(n -> n, n -> new HashSet<>()));
while (pdNum-- > 0) {
tokenizer = new StringTokenizer(reader.readLine());
int sortedSingerNum = Integer.parseInt(tokenizer.nextToken());
int preSinger = Integer.parseInt(tokenizer.nextToken()), postSinger;
while (sortedSingerNum-- > 1) {
postSinger = Integer.parseInt(tokenizer.nextToken());
if (nextSingers.get(preSinger).add(preSinger = postSinger))
preSingerNum[postSinger]++;
}
}
List<Integer> singers = new ArrayList<>();
Queue<Integer> prepared = IntStream.rangeClosed(1, singerNum)
.filter(n -> preSingerNum[n] == 0).boxed()
.collect(Collectors.toCollection(LinkedList::new));
while (!prepared.isEmpty()) {
int node = prepared.poll();
singers.add(node);
nextSingers.get(node).stream()
.peek(n -> preSingerNum[n]--)
.filter(n -> preSingerNum[n] == 0)
.forEach(prepared::offer);
}
result.append(singers.size() == singerNum ?
singers.stream().map(String::valueOf).collect(Collectors.joining(" ")) : 0);
}