[백준] 2252. 줄 세우기

학생A가 선 다음에 B !!

B가 서려면 이전에 A가 서야함
🔜 위상정렬

# 2252. 줄 세우기 (위상정렬)
from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
# graph = [[0] * (n+1) for _ in range(n+1)] 메모리초과
degree = [0] * (n+1)   # 진입차수
queue = deque([])
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1

for i in range(1, n+1):
    if degree[i] == 0:
        queue.append(i)

while queue:
    student = queue.popleft()
    print(student, end=" ")
    for i in graph[student]:
        degree[i] -= 1
        if degree[i] == 0:
            queue.append(i)

1. a와 b사이 연결을 보여주는 graph를 그려준다.
2. 진입차수를 만든다; degree[i]: i학생이 서기 전에 먼저 서야하는 학생 수
3. 진입차수가 0인 것들을 queue로 옮긴다
4. queue에 있는 것들은 바로 서도 되는 학생들이기 때문에 pop한 다음 바로 출력한다.
5. 학생이 선 다음에는 그 학생과 연결되는 학생의 차수를 -1한다. (연결고리 제거)
6. queue가 빌 때까지 반복 (모든 학생이 설 때까지 반복)

메모리 초과

처음에는

graph = [[0] * (n+1) for _ in range(n+1)]

그래프를 짰는데, n이 36000개까지 들어올 수 있어서
총 메모리 = N^2이므로,
36001 * 36001에다가 정수형 4byte를 곱한 값 3.81GB가 되기때문에 메모리초과

개선

그래프는 a에 b가 연결되있다는 정보를 알려주는 용도이므로,

[[],
 [],
 [],
 []]

형태로 바꿔서

 graph[a].append(b)

한 후, graph[a]에 있는 애들의 연결을 끊어주는 식으로 수정하였다.

    for i in graph[student]:
        degree[i] -= 1