문제 정보
- 문제 번호 : 14567
- 문제 이름 : 선수과목
- 문제 링크 : https://www.acmicpc.net/problem/14567
- 정답 코드 : https://github.com/dalmengs/algorithm-solutions/blob/main/14567/main.py
- 난이도 : Gold 5
- 체감 난이도 : Silver 2
- 알고리즘 : 위상 정렬
문제 설명
전공 과목의 선수 조건들이 주어질 때, 각 과목을 모두 수강하기 위한 최소 학기 수를 구하는 문제이다.
문제 해결
위상 정렬의 예제급 문제인 선수 과목 문제이다.
위상 정렬의 기본적인 구현에 더해, 다음 정점을 살펴볼 때 다음 학기에 듣는 다고 생각하고 (현재 학기 + 1) 을 계속 배열에 저장해주면 된다.
정답 코드
Python
from collections import deque
n, m = map(int, input().split())
g = { i: [] for i in range(1, n + 1) }
indegree = [0 for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
indegree[v] += 1
q = deque()
sem = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
if indegree[i] == 0:
q.append([i, 1])
sem[i] = 1
while q:
now, se = q.popleft()
for next in g[now]:
indegree[next] -= 1
sem[next] = se + 1
if indegree[next] == 0:
q.append([next, se + 1])
print(" ".join(list(map(str, sem[1:]))))마무리
위상 정렬은 특히 그래프 DP와 많이 연결되어 출제되는 거 같다.
학기 업데이트 (se + 1)은 위상 정렬 중 큐에 들어가는 순간 해야 하는 것이 아닌, 매번 해줘야 한다는 점이 중요한 문제였다.
답글 남기기