[백준] 2252번 줄 세우기

문제 설명

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

문제 풀이

• 기본적인 위상 정렬 문제이다.
• 문제 로직상 사이클이 없는 단방향 그래프이므로 유추가능하다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N, M;
    public static int[] result;
    public static int[] inDeg;
    public static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();

    public static void solve() {
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++)
            if (inDeg[i] == 0) q.add(i);
        for (int i = 0; i < N; i++) {
            int cur = q.poll();
            result[i] = cur;
            for (int j = 0; j < edge.get(cur).size(); j++) {
                int y = edge.get(cur).get(j);
                if (--inDeg[y] == 0)
                    q.add(y);
            }
        }
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //초기화
        for (int i = 0; i <= N; i++)
            edge.add(new ArrayList<>());
        result = new int[N];
        inDeg = new int[N+1];
        for (int i = 0;i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            edge.get(from).add(to);
            inDeg[to]++;
        }
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        solve();
        for (int i = 0; i < N; i++)
            bw.write(result[i] + " ");
        bw.write("\n");
        bw.flush();
        bw.close();
        br.close();
    }
}