위상정렬 5594

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

 

 

위상정렬이란 ? 

"순서가 있는 작업" 문제를 푸는 알고리즘.

즉, 선행 관계가 있는 일들을 올바른 순서로 나열할 떄 사용한다.

 

핵심 개념

- 그래프 종류 : 방향 그래프 (사이클이 없는 그래프)

- 목적 : 모든 노드를 "선행 관계를 지키면서" 나열하기 

- 예시 : (1) 선수 과목이 있는 과목 순서 정하기 (2) 작업 간 선행 조건이 있는 공정 순서 (3) 빌드 의존성(어떤 파일을 먼저 컴파일해야 하는가)

 

동작 원리

1. 진입차수 (indegree) : 각 노드로 들어오는 간선의 개수를 계산한다.

2. 진입차수가 0인 노드(선행 조건이 없는 작업)부터 처리한다.

3. 해당 노드와 연결된 간선을 제거하면서, 새로운 진입차수가 0이 된 노드를 큐에 넣는다.

4. 큐가 빌 떄까지 반복한다. (처리 순서가 위상정렬 결과)

 

 

 

 

// 위상정렬 (사이클 없는 방향 그래프의 간선 방향을 거스르지 않도록 선형 순서로 나열하는 알고리즘)

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


public class Main{
    public static void main(String[] arge)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine()); // 팀 수
        int m = Integer.parseInt(br.readLine()); // 붙은 수
        ArrayList<Integer>[] graph = new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            graph[i] = new ArrayList<>();
        }
        
        int w, l;
        int[] outputs = new int[n+1];
        int[] inputs = new int[n+1];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            l = Integer.parseInt(st.nextToken());
            graph[w].add(l); // 진팀 연결하기
            outputs[w]++;
            inputs[l]++;
        }
        
        // 마지막이 0인지 1인지 판단 
        int countZero = 0;
        int last = 0;
        for(int i=1; i<=n; i++){
            if(outputs[i]==0){
                countZero++;
            }
        }
        if(countZero==1){
            last = 0;
        }else {
            last = 1;
        }
        
        StringBuilder sb = new StringBuilder();
        boolean[] visited = new boolean[n+1];
        Queue<Integer> queue = new LinkedList<>();
        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                if(inputs[i]==0){
                    queue.offer(i);
                }
                while(!queue.isEmpty()){
                    int now = queue.poll();
                    sb.append(now).append("\n");
                    for(int next : graph[now]){
                        if(!visited[next]){
                            inputs[next]--; // 진입차수 하나씩 줄여주기 
                            if(inputs[next]==0){ // [핵심] 순위가 확정되었을 때만 큐에 넣기
                                visited[next] = true;
                                queue.offer(next);
                            }
                        }
                    }
                }
            }
        }
        sb.append(last);
        System.out.println(sb);
    }
}

 

 

위상정렬의 핵심인 "진입차수"에 대한 처리를 제대로 안해줘서 헤멨던 문제다.

알고리즘을 제대로 익히자 !