★Topology Sort Advanced - 2 Solved★

★ 2252 줄 세우기 ★

import sys
input=sys.stdin.readline
from collections import deque

N,M=map(int,input().split())
indegree = [0] * (N+1)
graph = [[] for _ in range(N+1)]

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

result = []
queue = deque()

#1
for i in range(1,N+1):
    if indegree[i] == 0:
        queue.append(i)

#2
while queue:
    node = queue.popleft()
    result.append(node)
    for i in graph[node]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)

print(*result)

 

🚄 전형적인 위상정렬 문제

 

* A,B 가 주어졌을 때 A가 B의 앞에 서야 한다는, 순서 정보가 여러 개 주어졌을 경우, 이 순서에 맞추어 정렬하는 '위상 정렬' 문제

: 학생을 각 node로 하여, 순서 정보가 주어진 node 간의 간선 연결된 그래프에서의 위상 정렬 구하기.

: indegree list를 만들어, 각 node 별 indegree 정보 업데이트

: indegree가 0인 경우의 node를 처음에 queue에 넣고, queue를 돌려 node popleft()할 때마다 정렬 list에 넣고, popleft()한 node의 주변 node indegree -= 1 / 그리고 indegree 0인 node queue에 넣어서 계속 queue 돌림

 

🚄 위 문제의 경우 학생의 순서 정보에 맞게 graph 만들고, indegree 각 node별 list 만들어 최종적으로 줄 선 list 출력하면 끝

---

★ 2623 음악 프로그램 ★

import sys
input = sys.stdin.readline
from collections import deque

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

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


for _ in range(M):
    orders = list(map(int,input().split()))
    for i in range(len(orders)):
        node = orders[i]
        if i != 0 and i != len(orders)-1:
            graph[node].append(orders[i+1])
        
        if i != 0 and i != 1:
            indegree[node] += 1


queue = deque()
for i in range(1,len(indegree)):
    if indegree[i] == 0:
        queue.append(i)

ans = []
while queue:
    node = queue.popleft()
    ans.append(node)
    for next_node in graph[node]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)

if len(ans) != N:
    print(0)
else:
    print(*ans,sep='\n')

 

🚄 전형적인 위상정렬 문제이나, A -> B -> C와 같이 두 개 이상의 연속된 연결점 노드 묶음이 존재하는 문제.

: 두번째 node부터 끝까지의 node의 indegree += 1 / 그리고 첫번째 node부터 맨 끝 바로 앞의 node의 + 그 다음 node와 graph update

---