[BOJ 2623] 음악프로그램 (Java)

BOJ 2623 음악프로그램

난이도 : 골드 3

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

전략

위상정렬을 사용하여 풀 수 있는 문제임을 알 수 있다.

2252 줄세우기 문제와 비슷하지만 다른 점이 있다.

 

예제의 입력을 보면

이렇게 각 PD별로 가수의 순서를 정할 수 있는데, 1:1이 아니라 여러명의 가수의 순서를 정하는 것이다.

이로 인해 하나의 노드에서 여러 개의 링크를 가질 수 있다.

 

 

따라서 링크를 배열로 저장하여 해결하였다.

 

시행착오

오랜만에 백준을 푸니까 입력을 받을 때 실수가 있었다.

입력의 가수 순서 inputs[j]를 그냥 j로 사용하여서 의도와 다른 결과가 나왔다.

기초적인 실수지만 NullPointer, ArrayBound 등의 예외가 발생하지 않으므로 발견하기 어려워 앞으로 주의해야 할 것 같다.

 

코드

package BOJ_2623;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs;
        int N, M;

        inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);

        Node[] nodes = new Node[N + 1];
        // init
        for (int i = 0; i <= N; i++) {
            nodes[i] = new Node(i);
        }

        // read inputs
        for (int i = 0; i < M; i++) {
            inputs = br.readLine().split(" ");

            for (int j = 1; j < inputs.length - 1; j++) {
                int cur = Integer.parseInt(inputs[j]);
                int next = Integer.parseInt(inputs[j + 1]);
                nodes[cur].linking.add(nodes[next]);
                nodes[next].inDegree++;
            }
        }

        List<Node> sorted = topologySort(nodes);
        if (sorted == null)
            System.out.println(0);
        else
            sorted.forEach(n -> {
                System.out.println(n.num);
            });
    }

    private static List<Node> topologySort(Node[] nodes) {
        Queue<Node> queue = new LinkedList<>();
        List<Node> result = new ArrayList<>();

        for (int i = 1; i < nodes.length; i++) {
            if (nodes[i].inDegree == 0) {
                queue.offer(nodes[i]);
            }
        }

        // for n times (exclude index 0)
        for (int i = 1; i < nodes.length; i++) {
            if (queue.isEmpty()) {
                return null;
            }

            Node cur = queue.poll();
            for (Node link : cur.linking) {
                link.inDegree--;
                if (link.inDegree == 0) {
                    queue.offer(link);
                }
            }

            result.add(cur);
        }

        return result;
    }

    static class Node {
        final int num;
        int inDegree = 0;
        List<Node> linking = new ArrayList<>();

        public Node(int num) {
            this.num = num;
        }
    }

}

 

깨달은 점

간만에 백준을 풀려고 하니까 손도 머리도 다 잘 안따라준다..

그래도 차근차근 요구사항을 읽고 그림을 그린 덕분에 헤매지 않고 바로 구현할 수 있었다.

여유를 가지는게 더 빨리 가는 길일 수도 있겠다고 생각했다..