[백준] 선수과목 - 14567번

문제

 

https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

 

내가 하는 이해

 

예제 입력 1을 생각해보면,  3번과목을 듣기 위해서는 2번과목을 선수해야하고 또 그 2번과목을 듣기 위해서는 1번과목을 선수해야 한다.

즉 1 -> 2 -> 3 순으로 이수해야 한다.

 

동일하게 예제 입력  2를 생각해보면,

1 -> 2 -> 5

1 -> 3

4 -> 5

위와 같이 1 -> 2 -> 5, 4 -> 5 처럼 5번 과목의 입장에서 생각할 때, 독립적인 깊이를 가진 여러 선수과목 코스가 생길 수도 있다.

 

첫번째의 아이디어는 각 과목간 이어진 edge를 반대로 돌려 dfs로 깊이를 구해 그 최소의 값을 찾아보는 것이었다.

하지만, 이는 노드의 갯수가 1000이고 조건이 500,000정도여서 각 노드에서 모든 탐색을 해주기엔, 시간복잡도에서 어려움이 있어 보인다. 

 

그래서 찾아낸 방법은 Topological Sort 즉 위상정렬의 기법이다.

 

 위상정렬은, DAG(Directed Acyclic Graph)인 그래프이고 이 백준의 선수과목 문제는 해당 알고리즘의 정석적인 활용이다.

 

 위상정렬 알고리즘은 노드로 들어오는 엣지가 0(indegree == 0)인 노드가 무조건 있어야 하는데,

만약, 0인 노드가 없다면, 모든 노드들은 자신에게 들어오는 엣지가 있는 것이고 이는 곧 그래프가 사이클을 가지고 있다는 것이기 때문이다.

 

 

때문에 해당 특징을 문제에 반영해보면,

 '각 선수과목당 들어가는 엣지가 0인 과목(선수과목이 없는 과목)을 Queue에 넣고, 해당 과목이 다음 선수과목으로 이어지는 엣지를 제거해 indegree가 0이 되는 과목을 Queue에 다시 넣어준다.' 라는 과정을 반복하는 것이다.

 

이를 코드로 나타내면, 아래와 같다.

 

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = defaultdict(list)

answerNode = [0] * (N+1)
indegreeZeroSet = set()

for i in range(M):
    s, e = map(int, input().split())
    graph[s].append(e)
    indegreeZeroSet.add(e)
    answerNode[e] += 1

q = deque()
count = 1
answer = [0] * (N+1)

# indegree가 0 인놈을 순서대로 큐에 넣어서 제거해줌
for i in range(1, N+1):
    if i not in indegreeZeroSet:
        q.append([i, count])
        answer[i] = count

while q:
    target, targetCount = q.popleft()
    answer[target] = targetCount

    for node in graph[target]:
        answerNode[node] -= 1
        if answerNode[node] == 0:
            q.append([node, targetCount+1])


print(*answer[1:])