[파이썬/python] 백준 - 14567 선수과목 (Prerequisite)

 

문제

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

---

문제 설명

1.   Z대학에 있는 과목들은 선수과목이 존재하여 해당되는 모든 과목을 이수해야만 해당 과목을 이수할 수 있다.
   1. 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
   2. 모든 과목은 매 학기 항상 개설된다.
2. 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하라

 

---

풀이

첫 번째 예제를 통해 문제를 이해해 보자.

3 2
2 3
1 2

N = 3, M = 2 과목은 총 3개, 선수 조건의 수는 2개이다.

 

선수과목은 다음과 같다.

1. 2번 과목을 수강해야 3번 과목을 수강할 수 있음

2. 1번 과목을 수강해야 2번 과목을 수강할 수 있음

 

그렇다면 결국 1번 과목을 수강해야 2번 과목을 수강하고, 3번 과목을 수강할 수 있다.

1 -> 2 -> 3와 같은 구조로 나타낼 수 있겠다.

 

그럼 이제 생각해 보자.

화살표가 가리키는 과목은 선수과목이 필요하고 화살표가 들어오지 않는 과목은 당장이라도 들을 수 있다는 의미이다.

 

위와 같은 구조를 트리의 형태로 다시 보면 아래와 같은 그림처럼 표현할 수 있다.

원리에 대해 다시 말하자면 현재의 노드로 들어오는 간선을 진입 간선이라고 하겠다.

그럼 현재 과목(노드)의 진입간선이 없다면, 해당 과목을 들을 수 있다는 뜻이다.

 

먼저 1 과목을 들으면 2-> 3이 되므로 2의 진입 간선이 사라지게 된다. 그럼 2 과목을 들을 수 있고 마지막으로 3 과목을 들을 수 있다.

진입 간선은 1개보다 더 많이 존재할 수 있다. 즉 선수과목이 많아질 수 있다는 말이다.

그럴 때 노드의 진입 간선의 개수를 진입 차수이라고 부른다.

 

따라서 이 문제에서는 진입 차수가 없는 노드부터 순차적으로 탐색하면서 다음 노드의 진입 차수를 감소시키고 결괏값을 찾는 문제이다.

 

즉 진입 차수에 따른 탐색을 할 때 쓰는 알고리즘인 위상정렬을 통해 문제를 풀이했다.

 

먼저 노드들의 초기 진입차수들을 배열에 갱신한다. 그 후 인접 리스트 방식으로 그래프를 생성한다.

Queue를 사용하여 현재 진입차수가 0인 노드들을 넣은 후, 차수가 0이 되는 노드마다 cost를 1씩 늘렸다.(Cost = 학기)

 

queue에서 나오는 노드는 무조건 차수가 0이기 때문에 바로바로 결과 값을 갱신하며 탐색했다.

 

선수 과목 개념은 위상정렬의 대표적인 예시라고 생각한다. 상대적으로 어려운 알고리즘이지만 선수 과목이라는 개념으로 설명하면 누구나 쉽게 이해할 수 있을 듯하다.

 

 

 

 

 

---

코드

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

n,m = map(int,input().split())

degree = [0 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]

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

queue = deque()
res = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if degree[i] == 0:
        queue.append((i,1))


while queue:
    v1, depth = queue.popleft()
    res[v1] = depth
    for v2 in graph[v1]:

        if degree[v2] > 0:
            degree[v2] -= 1

            if degree[v2] == 0:
                queue.append((v2,depth+1))
    
print(*res[1:])

---

시간복잡도

• 위상정렬의 시간복잡도는 그래프의 탐색 시간이기 때문에 $O(V + E)$이다.
• 최악의 경우 $V = 1000, E = 500,000$이므로 약 $O(5*10^5)$정도의 시간복잡도를 가진다.