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

접근 방법

1. 순서가 있는 노드... 위상 정렬이 절로 떠오르는 문제 설명이다. 위상 정렬 알고리즘을 구현하기만 하면 정답을 맞출 수 있는 문제이다.
2. 입력 제한을 보면 가수가 최대 1000명이 나온다고 하니까 O(N ** 2)까지 두고 풀어도 널널한 느낌이기 때문에, 빈 배열을 찾을 때 그냥 단순 순회하도록 구현한다.
   1. 차례대로 뺄 노드를 담을 Queue를 하나 만든다.
   2. 각 노드에 대한 조건 노드를 리스트로 둔다.
   3. Queue에서 노드를 하나씩 뺄 때마다 모든 노드를 순회하면서 뺀 노드가 존재한다면 리스트에서 빼준다.
   4. 위의 단계를 진행한 결과 빈 리스트가 나오게 된다면, 해당 노드를 Queue에 추가해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 1; i <= n; i++) map.put(i, new HashSet<>());

        // per PD
        for (int i = 0; i < m; i++) {
            String[] orders = br.readLine().split(" ");
            if (orders.length == 1) continue;
            for (int j = 2; j < orders.length; j++) {
                int node = Integer.parseInt(orders[j]);
                if (!map.containsKey(node))
                    map.put(node, new HashSet<>());
                map.get(node).add(Integer.parseInt(orders[j - 1]));
            }
        }

        Deque<Integer> q = new ArrayDeque<>();
        List<Integer> answer = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (map.get(i).size() == 0) q.add(i);
        }

        while (!q.isEmpty()) {
            int currentNode = q.pollFirst();
            answer.add(currentNode);
            for (int i = 1; i <= n; i++) {
                if (map.get(i).contains(currentNode)) {
                    map.get(i).remove(currentNode);
                    if(map.get(i).size() == 0) q.add(i);
                }
            }
        }

        if (answer.size() != n) System.out.println(0);
        else for (int num : answer) System.out.println(num);
    }
}

복기

배열 및 래퍼 클래스를 다룰 때는 항상 null 조건을 생각하고 코딩하기