줄 세우기 [백준 2252][골드2][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

2252번: 줄 세우기

위상정렬을 공부해 보았다.

위상정렬은 어떤 일의 순서를 찾는 알고리즘으로써 

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다.

 

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

public class 줄세우기 {
    static int N; // 그래프 정점의 수
    static int M; // 간선의 수

    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("test.txt"));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        int[] Link = new int[N + 1]; // 간선의 수에 대한 배열
        
        //인접리스트
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < N + 1; i++) {
			graph.add(new ArrayList<Integer>());
		}
        //단방향 설정
        for (int i = 0; i < M; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			graph.get(A).add(B);
			Link[B]++;
		}
        
        Sort(graph, Link);
    }
    public static void Sort(ArrayList<ArrayList<Integer>> graph, int[] Link) {
    	Queue<Integer> q = new LinkedList<>();
    	//1. 입선의 갯수가 0인 노드를 담는다.
    	for (int i = 1; i < N+1; i++) {
			if(Link[i] == 0) {
				q.add(i);
			}
		}
    	// 노드 수만큼 반복
    	for (int i = 0; i < N; i++) {
    		int node = q.poll();
    		//노드를 출력
    		System.out.print(node + " ");
    		
    		// 노드에 연결된 모든 노드들
    		for (int nextNode : graph.get(node)) {
				Link[nextNode]--;
				
				//입선의 갯수가 0인 노드를 담는다.
				if(Link[nextNode] == 0) {
	    			q.add(nextNode);
	    		}
			}
		}
    }
}

 위상정렬이 잘 정리된 블로그를 보고 공부했다!

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html