[S/W 문제해결 응용] 10일차 - 작업순서 D6

 

 

 문제는 위와 같다.

 

간단하게 정리하자면 작업들에는 먼저 선행해야할 작업들이 있고,

 

이 작업들을 모두 수행하는 순서를 출력하라는 것이다. 

 

위상정렬을 사용해서 출력하면된다. 

 

위상정렬 알고리즘을 통해  Queue에 넣고 

 

Queue에서 빼내면서 차례대로 출력을 하면 된다.

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static int V,E;
    static LinkedList<Integer>list[];
    static int [] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int t=1;t<=10;t++) {
            bw.write("#"+t+" ");
            StringTokenizer st= new StringTokenizer(br.readLine());
            V=Integer.parseInt(st.nextToken());
            E=Integer.parseInt(st.nextToken());
            st=new StringTokenizer(br.readLine());
            list=new LinkedList[V+1];
            for(int i=0;i<=V;i++) {
                list[i]=new LinkedList<>();
            }
            arr=new int [V+1];
            for(int i=0;i<E;i++) {
                int a=Integer.parseInt(st.nextToken());
                int b= Integer.parseInt(st.nextToken());
                list[a].add(b);
                arr[b]++;
            }
            Queue<Integer> q= new LinkedList<>();
            for(int i=1;i<=V;i++) {
                if(arr[i]==0)
                    q.add(i);
            }
            while(!q.isEmpty()) {
                int tmp =q.poll();
                bw.write(tmp+" ");
                arr[tmp]--;
                for(int i=0;i<list[tmp].size();i++) {
                    if(--arr[list[tmp].get(i)]==0) {
                        q.add(list[tmp].get(i));
                    }
                }
            }
            bw.newLine();
        }
        bw.close();
        br.close();
    }
}