[Do It! 코딩테스트 자바편(김종관)] 문제 053(백준 2252번)

느낀점

• 위상 정렬을 써야 함을 알고 접근하니 풀 시도는 할 수 있었다.
• 처음 위상 정렬 구현할 때 배열과 ArrayList만 가지고 하려 해서 애를 먹었다. 이 때 큐를 쓸 수 있음을 교재를 본 후 깨달았다.

문제

줄 세우기 (백준: 2252번)

풀이

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

public class Main {
    static ArrayList<Integer>[] adjacencyList;
    static int[] inDegreeArr;
    static ArrayList<Integer> sortedArr;
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 진입 차수 배열과 인접리스트 초기화
        inDegreeArr = new int[n + 1];
        adjacencyList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adjacencyList[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjacencyList[a].add(b);
            inDegreeArr[b]++;
        }

        sortedArr = new ArrayList<>();
        topologySort();
        for (int i = 0; i < n; i++) {
            System.out.print(sortedArr.get(i) + " ");
        }
    }

    private static void topologySort() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegreeArr[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int now = queue.remove();
            sortedArr.add(now);
            for (int next : adjacencyList[now]) {
                inDegreeArr[next]--;
                if (inDegreeArr[next] == 0) {
                    queue.add(next);
                }
            }
        }

    }
}