백준: 14567 선수과목(Prerequisite)

문제

14567번: 선수과목 (Prerequisite)

 

문제 풀이

 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다. 이에 대한 개념을 이해하였다면 위상 정렬을 그대로 구현한 후, 다음 조건을 이해하면 쉽게 답을 찾을 수 있다.

 

예제 입력2를 그래프로 표기

• 위상 정렬을 이용하면 탐색 순서는 1, 4, 6, 2, 3, 5이다.
• 1, 4, 6 과목은 선수 과목(진입 차수가 0)이 없다.
  • 선수 과목이 없는 경우이므로 1학기에 수강할 수 있다.
• 2, 3의 경우 진입 차수가 1이고, 선수 과목은 1이다.
  • 선수 과목이 있으므로 1번 과목을 수강한 이후에 수강할 수 있다.
• 5번 강의는 선수 과목이 2, 4 이므로 2개 모두 수강하여야 수강할 수 있다.

 선수 과목이 존재하는 경우는 queue를 통해 진입 차수를 감소하는 과정에서 선수 과목의 수강 학기를 고려한 결과를 반영하여야 한다. 이는 `현재 수강 과목의 학기 = 선수 수강 과목의 학기 + 1`이 된다. 이는 위상 정렬을 통해, 선수 과목(진입 차수)이 많은 과목(노드)은 차후에 처리되기 때문에 가능하다.

 

 즉, 2, 3 과목의 경우 1 과목이후에 수강하여야 하므로 2학기에 수강할 수 있다. 5 과목의 경우 4 과목 이후에 수강하는 조건이라면 2가 되겠지만 2 과목 이후의 수강이라는 조건도 있으므로 2 + 1이 되어 3학기에 수강할 수 있다. 따라서 이를 코드로 구현하면 문제에서 찾고자 하는 답인 `1 2 2 1 3 1`을 구할 수 있다.

 

코드

from sys import stdin
from collections import deque

PRE, IN_DEGREE = 0, 1

if __name__ == "__main__":
    N, M = map(int, stdin.readline().split())
    # 인덱스를 1번 부터 사용하기 위해 + 1
    result = [1] * (N + 1)
    subject = [[set(), 0] for _ in range(N + 1)]

    # 하위 과목들과 진입 차수 증가
    for _ in range(M):
        A, B = map(int, stdin.readline().split())
        subject[A][PRE].add(B)
        subject[B][IN_DEGREE] += 1

    q = deque()

    for idx, values in enumerate(subject):
        if not idx:
            continue

        prerequisite, in_degree = values
        # 최초 진입 차수가 0 인 경우, queue에 삽입
        if in_degree == 0:
            q.append(idx)

    while q:
        cur_subject = q.popleft()
        prerequisites = subject[cur_subject][PRE]

        for pre in prerequisites:
            subject[pre][IN_DEGREE] -= 1

            # 진입 차수가 0이라면, queue에 삽입 후 학기 수 파악
            if subject[pre][IN_DEGREE] == 0:
                q.append(pre)
                result[pre] = result[cur_subject] + 1

    print(*result[1:])