[PS] 음악프로그램 (백준 2623번)

위상 정렬 문제이다. 이번에는 Java로 풀어보았다. 생각보다 변수명을 신경쓰고, 메서드 단위로 쪼개서 구현하는게 쉽지 않다. 특히 객체지향을 녹여내는 건 더욱 그렇다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer stringBuffer;
    static Deque<Integer> queue;
    static ArrayList<Integer>[] adj;
    static int[] indeg;
    static String[] answer;
    static int N, M;

    public static void main(String[] args) throws IOException {
        input();
        process();
        print();
    }

    static void input() throws IOException {
        String[] inputs = bufferedReader.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);

        int LIST_SIZE = N+1;
        adj = new ArrayList[LIST_SIZE];
        indeg = new int[LIST_SIZE];
        queue = new ArrayDeque<>(LIST_SIZE);
        answer = new String[N];
        stringBuffer = new StringBuffer(3 * LIST_SIZE); // 줄바꿈 포함
        StringTokenizer stringTokenizer;

        for (int i = 1; i < LIST_SIZE; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int numberOfEdge = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            int firstNode = Integer.parseInt(stringTokenizer.nextToken());

            for (int j = 0; j < numberOfEdge; j++) {
                int tmp = Integer.parseInt(stringTokenizer.nextToken());
                adj[firstNode].add(tmp);
                indeg[tmp]++;
                firstNode = tmp;
            }
        }
    }
    
    static void process() {
        boolean flag = false;
        for (int i = 1; i < N+1; i++) {
            // queue 에다가 indeg가 0인 노드들을 담는다.
            if (indeg[i] == 0) {
                queue.add(i);
                flag = true;
            }
        }

        if (!flag) {
            System.out.println(0);
            System.exit(0);
        }

        // decreaseIndegAndLineUp(queue.pop(), 0); 
        
        // i가 가르키는 노드들에 대한 indeg 감소
        // 노드들을 꺼내면서 줄을 세우고, 꺼낸 노드들이 가리키는 노드들의 indeg 감소시킴.
        decreaseIndegAndLineUp(); 
        
    }

    static void decreaseIndegAndLineUp() {
        
        int count = 0;

        while (!queue.isEmpty()) {
            int node = queue.pop();
            for (int nextNode : adj[node]) {
                indeg[nextNode]--;
                if (indeg[nextNode] == 0) queue.add(nextNode);
            }
            stringBuffer.append(node);
            stringBuffer.append("\n");
            count++;
        }

        if (count != N) {
            stringBuffer.delete(0, stringBuffer.length());
            System.out.println(0);
            System.exit(0);
        }
    }

    static void print() {
        System.out.println(stringBuffer.toString());
    }

    static void decreaseIndegAndLineUp(int node, int answerIdx) {
        
        answer[answerIdx++] = String.valueOf(node);
    
        for (int nextNode : adj[node]) {
            indeg[nextNode]--;
            if (indeg[nextNode] == 0) decreaseIndegAndLineUp(nextNode, answerIdx++);
        }
    }
}

부족한 점이나 피드백은 사랑입니다 :)