위상 정렬 사용하면
과목 순서대로 나온다.
하지만
최소 학기를 구하려면 진입 차수가 같은 노드 끼리 묶어야 하는데
어떻게 해야 할지 모르겠다.
# 선수 과목 14567번 - 그래프로 입력받기
import sys
from collections import deque
# 입력: 과목 수 n, 선수 조건의 수 m
v, e = map(int, sys.stdin.readline().split())
# 과목을 순서대로 나열할 리스트를 만든다.
indegree = [0] * (v + 1) # 부모 테이블 초기화
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v + 1)]
# 각 과목의 최소 학기를 모두 1로 초기화
lst = [1 for _ in range(n+1)]
# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b) # 정점 A에서 B로 이동 가능
# 진입차수를 1로 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
q = deque()
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
now = q.popleft()
lst.index(now)
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 브론즈4에서 한 달 티어 목표 (0) | 2023.01.05 |
---|---|
코드업 1099번문제 - 개미 경로 찾기 (0) | 2022.06.22 |
[백준] 홀짝 칵테일 21312번 풀이 (0) | 2022.06.02 |
[이코테] 15강. 최소 공통 조상 알고리즘 (0) | 2022.06.01 |
[이코테] 14강. 자료구조: 바이너리 인덱스 트리 (0) | 2022.06.01 |