[ 백준 ] 2623 음악프로그램

Link | 백준 2623번 문제 : 음악프로그램

📌 About

특정 가수의 순서가 오려면 이전 가수들의 순서가 선행되어야 한다.

Graph 입장에서 보면 node의 탐색에 선행 node 탐색이 필요하다.

그렇기 때문에 위상정렬을 통해 해결할 수 있다.

위상 정렬

📌 Solution

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을 출력한다.

같다면 출연자들의 출연 순서를 출력한다.

📌 Code

GitHub Repository

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);
}