백준 2252(줄 세우기) - Python(파이썬) - 위상정렬

2252번: 줄 세우기

위상 정렬 설명 

CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)

💻 Python(파이썬)

import sys
from collections import deque

#학생 수, 학생 순서
n,m = map(int, sys.stdin.readline().split())
#학생 순서 그래프
graph = [[] for _ in range(n+1)]
#진입차수표
table = [0]*(n+1)

#학생 수만큼 입력 받기
for i in range(m):
    # 학생 순서 입력
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    table[b]+=1

#큐 구현
q = deque()
for i in range(1,n+1):
    #진입차수표가 0인 경우 큐에 삽입
    if table[i]==0:
        q.append(i)

#큐가 빌때까지 진행
while q:
    #현재 값 Pop
    now = q.popleft()
    #연결된 노드
    for i in graph[now]:
        table[i]-=1#1씩 제거
        #진입차수가 0인 값은 큐에 다시 삽입
        if table[i]==0:
            q.append(i)
    print(now,end=" ")

💻Java(자바)

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int[] table = new int[n+1];

        for(int i=0;i<n+1;i++){
            graph.add(new ArrayList<>());
        }

        //그래프 입력받기
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            table[b]++;
        }
        Queue<Integer> q = new LinkedList<>();
        //큐에 진입차수가 0인 값 입력
        for(int i=1;i<n+1;i++){
            if(table[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i:graph.get(now)){
                table[i]-=1;
                if(table[i]==0){
                    q.offer(i);
                }
            }
            System.out.print(now+" ");
        }
    }
}