[파이썬] SWEA 1267 : 작업 순서 (test)

[파이썬] SWEA 1267 : 작업 순서 (test)

• SWEA 1267 : 작업 순서

---

풀이

방향성 생각

• 위상 정렬 기본문제.
• 진입차수 관리해주면서 큐에 계속 넣어주기.

 

전체코드

from collections import deque

TC = 10
for tc in range(1,TC+1):

    N,M = map(int,input().split())
    infos = list(map(int,input().split()))

    G = [[] for _ in range(N+1)]
    for i in range(M):
        a,b = infos[2*i:2*i+2]
        G[a].append(b)

    # 진입차수 체크
    rank = [0]*(N+1)
    for x in range(1,N+1):
        for y in G[x]:
            rank[y] += 1

    # 진입차수 0인거 큐에 넣기
    Q = deque()
    for x in range(1,N+1):
        if not rank[x]:
            Q.append(x)

    # 반복해서 진입차수 관리해주기.
    answer = []
    while Q:
        x = Q.popleft()
        answer.append(x)

        for nx in G[x]:
            rank[nx] -= 1
            if not rank[nx]:
                Q.append(nx)

    print(f"#{tc}", end=' ')
    print(*answer)

코멘트

• .