백준 14567 선수과목 (Prerequisite) 파이썬 풀이

난이도 : 골드5
풀이일 : 2405013
https://www.acmicpc.net/problem/14567

---

문제 캡쳐

---

아이디어

• 각 과목을 수강하기 전에 이수하여야 하는 선수 과목의 수를 센다.
• 선수 과목이 없는 과목에 대해, 해당 과목을 이수한 후 수강할 수 있는 과목들의 선수과목 수를 줄인다.
• 선수 과목이 남아있지 않은 과목들은 몇 번째 학기에 들을 수 있는지 기록한다.

---

전체 풀이코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
order = [1] * N  # 수강 가능한 학기
previous = [0] * (N + 1)  # 선수과목의 수
after = [[] for _ in range(N + 1)]  # 다음 과목

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    previous[B] += 1  # 선수과목 수 반영
    after[A].append(B)  # 다음 과목 정보 저장

# 선수과목이 없는 과목 queue 추가
queue = deque([i for i in range(1, N + 1) if not previous[i]])

while queue:
    x = queue.popleft()
    # 현재 과목 다음 과목들의 선수과목 수 조정
    for nx in after[x]:
        previous[nx] -= 1
        # 다음 과목의 모든 선수과목을 수강한 경우 학기 기록, queue 추가
        if not previous[nx]:
            order[nx - 1] = order[x - 1] + 1
            queue.append(nx)

print(*order)

---

상세 풀이코드

N, M = map(int, sys.stdin.readline().split())
order = [1] * N  # 수강 가능한 학기
previous = [0] * (N + 1)  # 선수과목의 수
after = [[] for _ in range(N + 1)]  # 다음 과목

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    previous[B] += 1  # 선수과목 수 반영
    after[A].append(B)  # 다음 과목 정보 저장

• order : 각 인덱스 과목을 몇 번째 학기에 수강할 수 있는지 기록할 배열
• previous : 각 인덱스 과목을 수강하기 전에 이수하여야 하는 선수 과목의 수 기록
• after : 해당 과목 이후에 들을 수 있는 과목들의 정보를 기록할 이차원 배열
• for 반복문 : 주어지는 선수과목 정보를 받아, previous, after 배열을 조정한다.

 

# 선수과목이 없는 과목 queue 추가
queue = deque([i for i in range(1, N + 1) if not previous[i]])

• 선수과목이 없는 과목은 첫 학기에 수강할 수 있다.
• 1부터 N + 1까지의 범위 숫자에 대해, previous[i] 가 0인 숫자를 queue에 추가한다.

 

while queue:
    x = queue.popleft()
    # 현재 과목 다음 과목들의 선수과목 수 조정
    for nx in after[x]:
        previous[nx] -= 1
        # 다음 과목의 모든 선수과목을 수강한 경우 학기 기록, queue 추가
        if not previous[nx]:
            order[nx - 1] = order[x - 1] + 1
            queue.append(nx)

print(*order)

• queue가 있는 동안 while 반복문을 수행한다.
• 현재 과목을 queue 왼쪽에서 뽑아내고, 현재 과목 x 이후에 들을 수 있는 과목들 nx에 대해 for 반복문을 수행하며, nx의 선수과목 수를 줄인다.
• 만약, 이 과정에서 선수과목이 0이 된 nx가 있다면, order에 순서를 현재 과목 x의 학기 다음 학기로 기록하고 queue에 nx를 추가한다.
• while 반복문이 종료된 후, order에 있는 요소를 한 칸씩 띄워 출력한다.