[김태원 알고리즘] 위상정렬 (그래프 정렬)

사용 언어: Python3

문제

풀이

from collections import deque

N, M = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]
in_degree = [0] * (N+1) # ✅ 진입 차수 (=나보다 먼저 실행되어야 하는 작업(=선행 작업)의 수)

for _ in range(M):
    s, e = map(int, input().split())
    G[s][e] = 1 # 방향 그래프 (='행' 작업을 먼저 하고나서 '열' 작업을 할 수 있다)
    in_degree[e] += 1 # ✅ 진입 차수 init

q = deque()
for i in range(1, N+1):
    if in_degree[i] == 0: # ✅ 어떤 작업의 진입 차수가 0이라는 말은 해당 작업을 바로 해도 된다 (선행 작업이 없음)
        q.append(i)

while q:
    cur = q.popleft()
    print(cur, end=' ') # cur 작업(=출력) 완료
    for i in range(1, N+1):
        if G[cur][i] == 1: # cur에서 i로 방향이 흐르고 있다면
            G[cur][i] = 0 # ✅ 1. 화살표 제거 (release)
            in_degree[i] -= 1 # ✅ 2. 후행 작업의 진입차수 감소
            if in_degree[i] == 0: # ✅ 진입 차수가 0이 되면 큐에 넣는다 (선행 작업이 없기 때문에 바로 실행할 수 있음)
                q.append(i)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기