2252번 - 줄 세우기

@mildsalmon·2022-01-25 09:37

1. 줄 세우기

난이도
- 골드 3
시간 제한
- 2초
메모리 제한
- 128 MB
출처
- 2252번: 줄 세우기 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 😊 1차 시도 (성공)

import sys
from collections import deque

input = sys.stdin.readline


def topology_sort(indegree: list) -> list:
    global lines

    q = deque()

    '''
    enumerate로 q에 student를 삽입하면, 0번째 인덱스가 반드시 들어가는 비효율적인 구조가 되어서, range로 변경함.
    '''
    # for i, value in enumerate(indegree):
    for i in range(1, len(indegree)):
        if indegree[i] == 0:
            q.append(i)

    answer = []

    while q:
        student = q.popleft()
        answer.append(student)

        for next_student in lines[student]:
            indegree[next_student] -= 1

            if indegree[next_student] == 0:
                q.append(next_student)

    return answer[::-1]


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    lines = [[] for _ in range(n+1)]
    indegree = [0 for _ in range(n+1)]

    for _ in range(m):
        A, B = list(map(int, input().split()))
        lines[B].append(A)
        indegree[A] += 1

    print(*topology_sort(indegree))