[백준 / 14567 번] 선수과목 파이썬

 

[ 전체 코드 ]

 

# N 과목수, M 선수 조건 수
N, M = map(int, input().split())

# dp 배열 생성
dp = [0 for _ in range(N+1)]

# 선수과목 갯수
ex_learn = [0 for _ in range(N+1)]
# 배울 수 있는 과목
can_learn = [[] for _ in range(N+1)]

# A번 과목이 B번의 선수과목 ( A<B )
for _ in range(M):
    A, B = map(int, input().split())
    # A에 배울 수 있는 과목 B 추가
    can_learn[A].append(B)
    # 선수과목에 차수를 하나 증가
    ex_learn[B] += 1  # 진입 차수

# 과목탐색을 위한 q 리스트 생성
q = []

# 선수과목이 없는 과목들 ( ex_learn == 0 )
for i in range(1,N+1):
    if ex_learn[i] == 0:
        # 진입차수가 0인 과목을 1로 해줌.
        dp[i] = 1
        # 과목탐색을 위해 q 리스트에 추가.
        q.append(i)

# q 가 더 이상 pop할게 없어지기 전까지 while문 반복
while q:
    # 현재 과목 cur 추출
    cur = q.pop(0)
    # cur 다음과목 next를 찾기 위한 과정
    for next in can_learn[cur]:
        # 이전에 배운 과목 ex_learn의 진입차수가 1인 경우
        if ex_learn[next] == 1:
            # 바로 다음과목으로 인식 후 1 더해줌.
            dp[next] = dp[cur]+1
            # 그후 q 리스트에 다시 추가
            q.append(next)
        # 선수과목 1개 탐색
        ex_learn[next] = ex_learn[next] - 1

# dp 배열에 저장된 것을 1번 인덱스 부터 차례로 호출
for j in range(1, N+1):
    print(dp[j], end=' ')

 

[ 결과 ]