위상 정렬 (with 백준 1005)

• 위상 정렬

 위상 정렬은 그래프의 정렬을 의미한다. 이를 위해서는 그래프가 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 할 필요가 있다. DAG란 간선이 단방향이어야 하며, 사이클이 존재하지 않는(어떤 노드를 출발했을 때 다시 그 노드로 돌아올 수 없는)그래프여야 한다.

 

 위상 정렬은 그렇게 어렵지 않다. 만약 아래와 같은 그래프가 있다고 하자. 

 동그라미 안에 있는 숫자는 노드의 번호이고 네모 안에 있는 숫자는 노드를 가리키는 간선의 개수이다.

간단하게 다음 규칙에 맞게 정렬을 해주면 된다.

 

(BFS 방법)

 1. 네모 안에 숫자가(노드를 가리키는 간선의 개수) 0인 노드들을 Queue에 넣어준다.

 2. Queue에서 노드 하나를 빼서 방문한 뒤 해당 노드의 간선들을 없애준다.

 3. 2번에 의해 자신을 가리키는 간선이 없어진 노드들의 네모 안의 값을 -1 해준다.

 4. 다시 1번부터 반복한다.

 

이 규칙에 맞게 노드를 방문한다면 각 그래프들의 선후 관계에 맞게 노드를 방문할 수 있다. 글로만 보면 어려우니 그림을 보며 이해해보자. 우선 위의 그림을 보면 1번 노드를 가리키는 간선이 없으므로 Queue에 1번 노드를 넣는다.

 

 큐에서 1번노드를 꺼내 방문한 뒤 1번노드와 연결된 간선을 모두 제거하면 위의 그림과 같이 된다. 2, 3번 노드는 원래 자신을 가리키는 간선이 1개씩 있었지만 방금 1번 노드를 방문하면서 그 간선들이 없어져 네모 안의 값이 0이 됐다.

 따라서 네모 안의 값이 0인 2, 3번 노드를 Queue안에 넣는다.

 

 그다음 Queue에서 2번노드를 꺼내 방문하고 간선을 없앤다. 그러면 5번 노드를 가리키는 간선의 개수가 0이 되므로 5번 노드를 Queue에 넣어주면 된다. 하지만 4번노드는 본인을 가리키는 간선이 1개 없어졌어도 아직 2개나 더 있으므로 Queue안에 넣지 않는다. 

 

 이런식으로 방문을 하다보면 아래와 같은 과정에의해 방문이 완료된다.

3번 노드 방문

 

5번 노드 방문

7번 노드 방문

4번 노드 방문

6번 노드 방문

 

 보는 것과 같이 위상 정렬은 어렵지 않고 관련문제를 한번만 풀면서 직접 코드를 짜본다면 금방 몸에 익을 것이다.

 

 그래서 위상 정렬에 관한 문제를 추천하자면 백준 1005번 ACM Craft"이다. https://www.acmicpc.net/problem/1005

내가 위상 정렬에 대해 공부하게 된 계기이며 풀면서 위상 정렬을 써야하는 이유를 알 수 있는 좋은 문제라 생각한다.

 

 해당 문제의 내용은 다음과 같다.

 건물을 N개 지을 수 있는데 각 건물들은 짓는 순서가 정해져있다(예를 들면 b를 지으려면 a를 지어야하는 것과 같다).

각 건물들의 짓는 순서와 짓는데 걸리는 시간이 주어졌을때 입력으로 주어지는 건물을 짓는 최소 시간을 구하여라.

(문제를 정말 간략하게 적었는데 직접 위 주소로 들어가 문제를 읽어보고 풀어보는 것도 좋다)

---

처음 위상 정렬을 모르고 여러 조건을 추가하며 노드를 방문해서 풀었을 때는 정답을 맞히긴 했지만 1500ms이상이 소요되었다. 하지만 위상 정렬을 이용하여 푸니 800ms까지 시간이 줄어들었고 훨씬 간단한 코드를 구현할 수 있었다. 코드는 다음과 같다.

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int[] time = new int[N + 1];
            int[] dp = new int[N + 1];
            ArrayList<Integer>[] lst1 = new ArrayList[N + 1];
            for (int i = 1; i < N + 1; i++) {
                lst1[i] = new ArrayList<>();
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i < N + 1; i++)
                time[i] = Integer.parseInt(st.nextToken());
            int[] in_degree = new int[N + 1];
            for (int i = 0; i < K; i++)
            {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                lst1[a].add(b);
                in_degree[b]++;
            }
            Queue<Integer> q = new LinkedList<>();
            int dest = Integer.parseInt(br.readLine());
            for (int i = 1; i < N + 1; i++) {
               if (in_degree[i] == 0)
                   q.add(i);
               dp[i] = time[i];
            }
            while (!q.isEmpty())
            {
                int n = q.poll();
                for (int next : lst1[n])
                {
                    in_degree[next]--;
                    dp[next] = Math.max(dp[n] + time[next], dp[next]);
                    if (in_degree[next] == 0)
                        q.add(next);
                }
            }
            sb.append(dp[dest]).append("\n");
        }
        System.out.print(sb);
    }
}

 

이 문제를 풀때 주요하게 생각한 점은 다음과 같다.

 

(위상 정렬)

 1. in_degree배열을 이용하여 노드를 가리키는 간선의 개수를 기록함

 2. Queue를 이용하여 노드 방문을 하였고 방문한 노드와 연결된 next노드의 in_degree를 -1해주며 in_degree가 0일때 Queue에 next노드를 넣음

 

(DP)

 1. 우선 배열 dp에 각 건물을 짓는데 걸리는 시간을 입력

 2. 노드를 방문하면 현재 노드의 건물을 짓는데 걸리는 시간을 이용하여 next노드의 건물을 짓는 시간을 결정함

 3. 만약 next노드의 건물을 짓는 시간이 이미 기록되어있다면 둘 중 더 큰 값으로 바꿈

 

다음과 같이 위상 정렬과 DP만 알면 어렵지 않게 풀 수 있는 문제이다.

 

 

 

---

reference

 - https://bcp0109.tistory.com/21