# 위상 정렬

* 위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.&#x20;
* 진입 차수는 자기 자신을 가리키는 에지의 개수입니다.&#x20;



### &#x20;줄 세우기&#x20;

#### Question - 2252&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FLgHhIrpeTNIXqLXn79Nc%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-08%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%203.58.50.png?alt=media\&token=68316650-0f21-47bf-8096-410186557bf8)

#### Code

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class N52_P2252_줄_세우기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int node = sc.nextInt();
        int edge = sc.nextInt();

        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= node; i++) { // 여기 1부터 넣어도 되지 않을까 ? 안된다.
            a.add(new ArrayList<>());
        }

        // 그래프, 진입 차수 동시에 처리 
        int[] in = new int[node + 1];
        for (int i = 0; i < edge; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();
            a.get(S).add(E);
            in[E]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= node; i++) {
            if (in[i] == 0) q.offer(i); // offer ??
        }

        while (!q.isEmpty()) {
            int now = q.poll();
            System.out.print(now + " ");
            for (int next : a.get(now)) {
                in[next]--;
                if (in[next] == 0) q.offer(next);
            }
        }
    }
}

```

#### Idea

#### reference



### 게임 개발하기&#x20;

#### Question - 1516

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FkaYKTEhNlSBjGMfPnQAa%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-08%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%203.59.44.png?alt=media\&token=e9eb7925-f5e2-4636-b641-db82b198408e)

#### Code

```java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N54_P1516_게임_개발하기 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int buildingNum = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= buildingNum; i++) {
            a.add(new ArrayList<>());
        }

        int[] in = new int[buildingNum + 1];
        int[] time = new int[buildingNum + 1];
        for (int i = 1; i <= buildingNum; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            while (true) {
                int preTemp = Integer.parseInt(st.nextToken());
                if (preTemp == -1)
                    break;
                a.get(preTemp).add(i);
                in[i]++;
            }
        }

        // 위상 정렬
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= buildingNum; i++) {
            if (in[i] == 0) {
                q.offer(i);
            }
        }

        int[] result = new int[buildingNum + 1];
        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next : a.get(now)) {
                in[next]--;
                result[next] = Math.max(result[next], result[now] + time[now]);
                if (in[next] == 0){
                    q.offer(next);
                }
            }
        }

        for (int i = 1; i <= buildingNum; i++) {
            System.out.println(result[i] + time[i]);
        }
    }
}

```

#### Idea

#### reference



### 임계 경로 구하기&#x20;

#### Question - 1948

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FQjQc9GSWIVvaa5cEjq9y%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-08%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%204.00.33.png?alt=media\&token=153b26fd-17de-436a-b327-32c528f84df9)

#### Code

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N55_P1948_임계_경로_구하기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node = Integer.parseInt(br.readLine()); // 도시
        int edge = Integer.parseInt(br.readLine()); // 도로

        // 출발 도시의 번호
        // 도착 도시 번호
        // 도로를 지나는 데 걸리는 시간

        ArrayList<ArrayList<dNode>> a = new ArrayList<>();
        ArrayList<ArrayList<dNode>> reverse = new ArrayList<>();

        // 그래프 초기화
        for (int i = 0; i <= node; i++) {
            a.add(new ArrayList<>());
            reverse.add(new ArrayList<>());
        }

        // 진입 차수 배열 : 자기 자신을 가리키는 에지의 개수
        int[] in = new int[node + 1];
        for (int i = 0; i < edge; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()); // 원리 좀 이해해
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            a.get(start).add(new dNode(end, time));
            reverse.get(end).add(new dNode(start, time));
            in[end]++;
        }

        // 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시
        StringTokenizer st = new StringTokenizer(br.readLine());
        int startDosi = Integer.parseInt(st.nextToken());
        int endDosi = Integer.parseInt(st.nextToken());

        // 위상 정혛
        Queue<Integer> q = new LinkedList<>();
        q.offer(startDosi);
        int[] result = new int[node + 1];
        while (!q.isEmpty()) {
            int now = q.poll();
            for (dNode next : a.get(now)) {
                in[next.targetNode]--;
                result[next.targetNode] =
                    Math.max(result[next.targetNode],
                        result[now] + next.value);
                if (in[next.targetNode] == 0) {
                    q.offer(next.targetNode);
                }
            }
        }

        // 위상 정렬 reverse
        int count = 0;
        boolean visited[] = new boolean[node + 1];
        q = new LinkedList<>();
        q.offer(endDosi);
        visited[endDosi] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (dNode next : reverse.get(now)) {
                // 1분도 쉬지 않는 도로 체크
                if (result[next.targetNode] + next.value == result[now]) {
                    count++;
                    if (visited[next.targetNode] == false) {
                        visited[next.targetNode] = true;
                        q.offer(next.targetNode);
                    }
                }
            }
        }
        System.out.println(result[endDosi]);
        System.out.println(count);
    }
}

class dNode {
    int targetNode;
    int value;

    dNode(int targetNode, int value) {
        this.targetNode = targetNode;
        this.value = value;
    }
}

```

#### Idea

* 개어렵 ㅁㅊ
* 이들이 출발 도시에서 출발한 후 도착 도시에서 만나기까지 걸리는 최소 시간과, 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수.

#### reference

