위상정렬(백준 2252번 줄세우기)

1. 위상정렬

---

위상정렬의 조건

위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다.

진입차수를 이용한 위상정렬

1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.

(방향 그래프 완성)

2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)

3. indegree가 0인 일을 모두 찾아 큐에 넣는다

4. 큐에서 정점 하나를 꺼낸다.

(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)

5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.

6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.

7. 큐가 빌 때까지 4~6을 반복한다.

---

2.위의 위상정렬을 이용한 백준 2252번 줄세우기 문제)

---

package graph;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class TopologySort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        Queue<Integer> queue =new LinkedList<Integer>();
        int n=sc.nextInt();
        int m=sc.nextInt();
        LinkedList<Integer>[] vertexArr = new LinkedList[n];
        for(int i=0;i<n;i++) {
            vertexArr[i]=new LinkedList<Integer>();
        }
        int[] indegree=new int[n];
        for(int i=0;i<m;i++) {
            int v=sc.nextInt();
            int w=sc.nextInt();
            vertexArr[v-1].add(w-1);
            indegree[w-1]+=1;
        }
        for(int i=0;i<n;i++) {
            if(indegree[i]==0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int x=queue.poll();
            System.out.print(x+1+" ");
            Iterator<Integer> it=vertexArr[x].iterator();
            while(it.hasNext()) {
                int y=it.next();
                indegree[y]--;
                if(indegree[y]==0) {
                    queue.offer(y);
                }
            }
        }
    }
 
}