백준 1766번 <문제집>

백준 알고리즘 1766번

www.acmicpc.net/problem/1766

1766번: 문제집

---

1766번

입력으로 첫 줄에 문제의 수 N과 먼저 푸는 것이 좋은 문제에 대한 정보의 수 M이 들어온다.

그 다음 M개의 문제에 대한 정보가 들어온다.

 

출력은 문제에 대한 정보에 맞게 민오가 풀어야 하는 순서대로 출력하면 된다.

---

문제 해결

먼저 푸는 순서가 있기 때문에 위상정렬 알고리즘을 사용하면 된다.

그리고 쉬운 문제를 먼저 풀어야 하니까 최소 힙을 사용했다.

문제의 번호를 vertex로 그리고 먼저 풀어야 하는 정보를 edge로 생각하고 위상정렬을 적용하면 된다.

 

먼저 푸는 문제에 대한 정보를 data에 인접 리스트 방식으로 저장해두었다.

indegree 리스트에 각 문제에 대한 indegree를 저장한다.

(index 접근을 쉽게 하기 위해 크기를 N+1로 했다. indegree = 특정한 노드로 들어오는 edge의 수)

 

일단 for문을 먼저 돌려서 최소힙에 indegree 리스트에서 값이 0이 index를 넣는다.

 

아래의 3개의 과정을 최소힙이 빌 때까지 반복한다.

1. 최소힙에서 가장 작은 값을 꺼내고 그 값을 result에 추가한다.

2. 값을 꺼냄으로써 그 값과 연결된 노드의 indegree의 값이 -1된다.

3. indegree 리스트의 값이 0이 되서 풀 수 있는 문제의 번호를 최소힙에 넣는다.

---

코드

import heapq

def main():
    n, m = map(int, input().split())

    data = [[] for i in range(n + 1)]
    indegree = [0 for i in range(n + 1)]

    for i in range(m):
        a, b = map(int, input().split())
        data[a].append(b)
        indegree[b] += 1

    result = []
    q = []

    for i in range(1, n + 1):
        if indegree[i] == 0:
            heapq.heappush(q, i)

    while q:
        temp = heapq.heappop(q)
        result.append(temp)
        for i in data[temp]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(q, i)

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

main()

---

결과

---

처음에 힙과 최단 경로 알고리즘을 배웠을 때 이 문제를 발견해서 어떻게 하는 거지!! 고민을 많이 하다가 못 풀었는데

위상정렬을 배우고 보니 바로 풀 수 있었다.