[BOJ] 2252. 줄 세우기

이 문제는 위상정렬(Topoologicl Sort)를 이용하는 문제이다.

위상정렬을 이용하기 위해선 DAG(Directed Acyclic Graph, 유향 싸이클없는 그래프)를 만족해야지 사용할 수 있다. 위상정렬이란 DAG의 정점들을 쭉 나열하였을 때 왼쪽에서 오른쪽(한바향)으로만 모든 간선이 이동하는 모양을 가지도록 정렬되게 하는 알고리즘이다. 즉 다음과 같은 모양으로 모든 정점이 정렬되는 것이다.

이러한 위상정렬을 하기위해선 우선적으로 싸이클이 없는 DAG임을 확인하고, 그다음 indegree배열을 사용하여 자신으로 들어오게 되는 간선의 수를 저장한다. 그 후 queue를 이용하여 indegree[index]=0이 되면 queue에 offer해주고 인접리스트를 돌면서 indegree들을 하나씩 줄여주는 과정을 반복한다. 즉 다음과 같은 과정을 가진다.

1.indegree가 0인 정점과 이와 연결된 모든 간선 지우기
2.남아있는 정점의 indegree 갱신
3.그래프의 모든 정점이 없어질 때까지 1과 2를 반복

자주나오는 알고리즘은 아니지만 개념을 확실히 이해하고 있을 필요가 있다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2252_줄세우기 {
    
    static int N;
    
    static List<Integer>[] graph;
    static int[] indegree;
    static boolean[] visit;
    
    static Queue<Integer> queue;
    
    public static void main(String[] args)  throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        
        graph=new ArrayList[N+1];
        for(int i=0;i<=N;i++)
            graph[i]=new ArrayList<>();
        
        indegree=new int[N+1];
        visit=new boolean[N+1];
        
        for(int i=0;i<M;i++) {
            st=new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken());
            int end=Integer.parseInt(st.nextToken());
            
            graph[start].add(end);
            indegree[end]+=1;
        }
        
        func();
        
    }
    
    static void func() {
        queue=new LinkedList<>();
        for(int i=1;i<=N;i++) {
            if(indegree[i]==0)
                queue.offer(i);
        }
        
        while(!queue.isEmpty()) {
            int cur=queue.poll();
            System.out.print(cur +" ");
            for(int next : graph[cur]) {
                indegree[next]-=1;
                if(indegree[next]==0)
                    queue.offer(next);
            }
        }
    }
}