[Algorithm/Java][백준] 2252번 줄 세우기

[BOJ] 2252번 줄 세우기

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

문제 접근

위상 정렬을 통해서 쉽게 푼 문제이다.
위상 정렬이란 순환이 없는 그래프에서 정점간의 순서를 구할 수 있는 알고리즘이다.
각각의 학생들을 정점이라고 생각하고, 입력으로 들어오는 순서들을 그래프들의 간선이라고 생각하면 쉽게 문제가 풀린다.
위상 정렬이란 우선 들어오는 간선의 개수를 세는 linkCnt의 값이 0인 정점들을 큐에 넣고, 하나씩 큐에서 빼면서 해당 정점과 연결된 정점들에 대해서 linkCnt를 -1 해주고 다시 linkCnt의 값이 0인 정점들을 큐에 넣는 방식으로 진행된다.

Code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ2252 {
    static int N;
    static int M;
    static int[] linkCnt;
    static ArrayList<ArrayList<Integer>> graph;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        linkCnt = new int[N + 1];
        graph = new ArrayList<>();
        for(int i = 0; i<=N; i++){
            graph.add(i, new ArrayList<>());
        }
        for(int i = 0; i<M; i++){
            int from = sc.nextInt();
            int to = sc.nextInt();
            graph.get(from).add(to);
            linkCnt[to]++;
        }
        System.out.println(topologicalSort());
    }
    public static String topologicalSort() {
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if(linkCnt[i] == 0) q.offer(i);
        }
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int v : graph.get(cur)) {
                linkCnt[v] --;
                if(linkCnt[v] == 0) q.offer(v);
            }
            sb.append(cur).append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}