백준 [N2252 - 줄 세우기]_위상정렬(Topological Sort)

줄 세우기 문제 설명

해당 문제는 위상정렬로 푸는 문제입니다. 

위상정렬은 그래프 정렬할 때 사용하는 알고리즘으로 그래프가 DAG(Directed Acyclic Graph, 방향성은 있지만 사이클은 없는 그래프)이여야 합니다.

 

풀이과정

필요한 자료구조는 다음과 같습니다.

ArrayList<Integer>[]	그래프 관계를 표현하는 인접리스트
int[] indegree	노드로 들어오는 간선 갯수를 담는 배열
Queue<Integer> queue	indegree가 0인 된 노드를 담는 큐
StringBuilder result	큐에서 꺼낸 노드를 출력하기 위한 StringBuilder

 

STEP1. list인접리스트에 순서를 저장하고, 노드를 가르키는 간선 수를 indegree배열에 저장합니다.

STEP2. queue에 indegree가 0인 노드를 담습니다.

STEP3. 큐에서 값을 꺼낸 노드를 result에 담고, 해당 노드가 가르키는 노드의 indegree를 1씩 감소합니다.

큐가 빌때까지 STEP3을 반복합니다.

 

전체코드

public class 줄세우기{
    private static int[] indegree;
    private static ArrayList<Integer>[] list;
    private static int N;
    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());
        int M = Integer.parseInt(st.nextToken());
        indegree = new int[N+1];
        list = new ArrayList[N+1];
        for(int i=1;i<=N;i++){
            list[i] = new ArrayList<>();
        }
        //STEP1
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            indegree[to]++;
            list[from].add(to);
        }
        br.close();
        topologicalSort();
    }

    public static void topologicalSort(){
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder result = new StringBuilder();
	
        //STEP2
        for(int i=1;i<=N;i++){
            if(indegree[i]==0) queue.add(i);
        }

		//STEP3
        while(!queue.isEmpty()){
            int node = queue.poll();
            result.append(node+" ");

            for(int nextNode : list[node]) {
                indegree[nextNode]--;
                if (indegree[nextNode] == 0){
                    queue.add(nextNode);
                }
            }
        }
        System.out.println(result.toString().trim());
    }
}