[알고리즘] 위상정렬 복습 겸 정리

💙 위상정렬

• 순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정하기위해 사용하는 알고리즘이다.
• 사이클이 없는 방향 그래프의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것이다.

사전 지식

1. DAG(Directed Acyclic Graph : 방향성 있는 비순환 그래프)

   

2. 진입 차수(in-degree)
   • 특정 노드로 들어오는 간선의 개수
   • 위상 정렬에서는 이 진입 차수를 이용하여, 진입 차수가 0이면 시작점이 된다.
3. 진출 차수(out-degree)
   • 특정 노드에서 나가는 간선의 개수

💙 위상정렬 구현(Queue 활용)

1. 먼저 모든 간선을 읽으며 indegree 테이블을 채운다.
2. indegree가 0인 정점들을 모두 큐에 넣는다.
3. 큐가 빌 때까지 반복 수행한다.
   1. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가한다.
   2. 해당 정점과 연결된 모든 정점의 indegree 값을 1 감소시킨다.
      • 이때 indegree==0이라면 큐에 추가한다.

즉, 큐에서 꺼내지는 순서가 위상 정렬을 수행한 결과이다.

💙 위상정렬 특징

1. 모든 정점을 방문하기 전에 큐가 공백 상태가 되면 사이클이 존재하는 것이다. (사이클이 존재하면 진입 차수가 0이 될 수 없음)
2. 그래프의 유형은 DAG(방향이 있는 비순환 그래프)
3. 여러 해답이 존재할 수 있다. (진입 차수가 0인 값이 동시에 생성이 된다면 작성한 코드 방법에 따라 답이 달라진다.)
4. 시간 복잡도 O (V+ E) (V : 노드 개수, E : 간선 개수)

---

아래의 코드는 백준의 위상정렬 기본 문제를 풀어본 예시 코드이다.

(2252번 : 줄 세우기)

static int N, M, indegree[], u, v;
static StringBuilder sb = new StringBuilder(); // 위상정렬 결과 저장
static Queue<Integer> q = new LinkedList<>();
static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
static ArrayList<Integer> get = new ArrayList<>();

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt(); M = sc.nextInt();
    indegree = new int[N+1];
    for(int i=0; i<=N; i++){list.add(new ArrayList<>());}
    // 1. 모든 간선을 읽으며 indegree[]를 채운다.
    for(int i=0; i<M; i++){
        u = sc.nextInt(); v = sc.nextInt();
        list.get(u).add(v); // u가 v보다 앞에 있어야 함
        indegree[v]++; // indegree 값 1 증가
    }
    // 2. indegree가 0인 정점들을 모두 큐에 넣는다.
    for(int i=1; i<=N; i++){if(indegree[i]==0)q.add(i);}
    // 3. 큐가 빌 때까지 반복수행한다.
    while(!q.isEmpty()){
        // 3-1. 큐에서 정점을 꺼내어 결과를 sb에 추가한다.
        int node = q.poll();
        sb.append(node + " ");
        // 3-2. 정점과 연결된 모든 정점의 indegree 값을 1 감소시킨다.
        get = list.get(node); // 정점과 연결된 모든 정점 리스트
        for(int i=0; i<get.size(); i++){
            int t = get.get(i);
            indegree[t]--;
            // indegree 값이 0이라면 큐에 추가한다.
            if(indegree[t]==0) q.add(t);
        }
    }
    System.out.println(sb);
}

참고자료

BaaaaaaaarkingDog :[실전 알고리즘] 0x1A강 - 위상 정렬