위상정렬 알고리즘

- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘.
- 사이클이 없음.
- 시간복잡도(노드 수:V, 에지 수: E) : O(V+E)
- 출력값이 항상 유일한 값으로 정렬되지 않습니다. -> 문제에 이러한 문구가 있으면 위상정렬로 시도해볼 수 있다!!

 

< 원리 이해 >

진입차수(indegree) 자기자신을 가리키는 에지의 개수

ArrayList<node>[N] (사이클없을때 사용)

1. 인접리스트, 진입 차수 배열 초기화
2. 진입차수 배열 초기 데이터 저장
3. 위상정렬 수행

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class P2252_줄세우기 {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    ArrayList<ArrayList<Integer>> A = new ArrayList<>();
    for (int i = 0; i <= N; i++) { //인접리스트 초기화
      A.add(new ArrayList<>());
    }
    int[] indegree = new int[N + 1];  // 진입 차수 배열 초기화
    for (int i = 0; i < M; i++) {
      int S = sc.nextInt();
      int E = sc.nextInt();
      A.get(S).add(E); // S - E 연결 
      indegree[E]++; // 진입차수 배열 데이터 저장하기[연결되어있는 것을 1로 변경해주는 작업]
    }
    Queue<Integer> queue = new LinkedList<>();  // 위상 정렬 수행
    for (int i = 1; i <= N; i++) {
      if (indegree[i] == 0) { // 0인 것들을 먼저 queue에 넣어준다
        queue.offer(i);
      }
    }
    while (!queue.isEmpty()) { // queue에 들어있는게 없을때 까지
      int now = queue.poll(); // queue의 맨위의 값
      System.out.print(now + " ");
      for (int next : A.get(now)) {
        indegree[next]--; // 1감소 되면서
        if (indegree[next] == 0) { // 0인것을 다시 queue에 넣어준다
          queue.offer(next); //queue에 넣어준다
        }
      }
    }
  }
}

참고: doitjava-p2252_줄세우기