[알고리즘 / 백준] 1766 - 문제집

www.acmicpc.net/problem/1766

1766번: 문제집

 

문제는 위와 같으며, 이 문제의 경우 위상 정렬에 대해 알고있다면 쉽게 문제를 해결할 수 있습니다.

 

위상 정렬(Topology Sort) 란, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주기 위해 사용하는 알고리즘입니다.

 

만약 위와 같은 순서대로 일이 진행되어야 한다면, 순서대로 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이런 순서대로 진행을 하면 됩니다. 이 순서는 다양하게 변경될 수 있습니다. (예, 1 -> 4 -> 2 -> 3 -> 5 -> 6 -> 7 도 가능합니다.)

 

하지만, 이 문제의 경우 순서대로 진행되면서 더 쉬운 문제(번호가 앞인 문제)가 더 빨리 풀려야 하기 때문에 heap 을 통해 문제를 해결하였습니다.

 

각 노드 별로 다음 연결되는 노드의 리스트를 담을 수 있도록 생성하고, 각 노드의 진입 차수를 저장합니다.

- 연결 노드 리스트 : [[], [2, 4], [3], [5], [6], [6], [7], []]

- 진입 차수: [0, 0, 1, 1, 1, 1, 2, 1]

 

그런 다음 진입 차수가 0인 데이터를 heap 에 먼저 넣고 heap 이 빈 값이 될 때까지 데이터를 뽑아 결과 리스트에 저장합니다. 이때 데이터를 뽑고 나면 해당 데이터 다음으로 실행되어야 하는 노드들은 진입 차수가 하나씩 줄어들고 이 노드들 중 진입 차수가 0이 되는 노드는 다시 heap 에 추가하여 반복적으로 일을 순서대로 처리할 수 있게 하면 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

n, m = map(int, stdin.readline().split())
array = [[] for _ in range(n + 1)]  # 해당 노드와 연결된 노드 담기
indegree = [0] * (n + 1)  # 진입 차수

heap = []

for _ in range(m):
    x, y = map(int, stdin.readline().split())
    array[x].append(y)  # x -> y 관계 연결
    indegree[y] += 1  # y 로 들어오는 진입 차수 증가

for i in range(1, n + 1):
    if indegree[i] == 0:  # 진입 차수가 0인 경우 heap 에 추가
        heapq.heappush(heap, i)

result = []
while heap:
    data = heapq.heappop(heap)
    result.append(data)
    for d in array[data]:  # 꺼낸 데이터와 연결된 데이터들을 돌면서
        indegree[d] -= 1   # 진입 차수 줄이기
        if indegree[d] == 0:  # 진입 차수가 0인 경우 heap 에 추가
            heapq.heappush(heap, d)

for i in result:
    print(i, end=" ")

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        List<ArrayList<Integer>> array = new ArrayList<>();
        for (int i = 0; i < nm[0] + 1; i++) {
            array.add(new ArrayList<>());
        }
        int[] indegree = new int[nm[0] + 1];

        for (int i = 0; i < nm[1]; i++) {
            int[] xy = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            array.get(xy[0]).add(xy[1]);
            indegree[xy[1]] += 1;
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 1; i < nm[0] + 1; i++) {
            if (indegree[i] == 0) {
                heap.add(i);
            }
        }

        StringBuilder result = new StringBuilder();
        while (!heap.isEmpty()) {
            int data = heap.poll();
            result.append(data).append(" ");

            for (int n : array.get(data)) {
                indegree[n] -= 1;
                if (indegree[n] == 0) {
                    heap.add(n);
                }
            }
        }

        System.out.println(result);
    }
}

 

이 문제는 위상 정렬을 이해하고 이를 heap 으로 구현할 수 있는 것이 핵심인 문제였습니다.