그래프-위상정렬

이론

📖 위상정렬
사이클이 없는 방향그래프에서 노드순서를 찾는 알고리즘.
시간복잡도 : O(v+e) , v=노드 수 e=에지 수

📍 위상정렬을 항상 유일한 값으로 정렬되지 않는다.

📍 사이클이 존재하면, 노드간의 순서를 명확히 정의할 수 없다. -> 위상 정렬 적용x

📖 진입 차수
자기 자신을 가리키는 에지의 개수.

문제풀이

📖 백준 2252 (🔗백준 2252 문제)

✏ 답이 여러 가지인 경우에는 아무거나 출력한다 -> 혹시 위상정렬문제??!

#위상정렬

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

n,m=map(int,input().split())
node=[[] for i in range(n+1)]
degree=[0]*(n+1)

for i in range(m):
    s,e=map(int,input().split())
    node[s].append(e)
    degree[e]+=1

queue=deque()

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

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

📖 백준 1516 (🔗백준 1516 문제)

✏ 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. -> 위상정렬문제??!

# 위상정렬

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

n=int(input())
node=[[] for i in range(n+1)]
degree=[0]*(n+1)
prod_time=[0]*(n+1)
result=[0]*(n+1)

for i in range(1,n+1):
    test=list(map(int,input().split()))
    prod_time[i]=(test[0])
    index=1
    while 1:
        temp=test[index]
        index+=1
        if temp==-1:
            break
        node[temp].append(i)
        degree[i]+=1

queue=deque()

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

while queue:
    now=queue.popleft()
    for i in node[now]:
        degree[i]-=1
        result[i]=max(result[i],result[now]+prod_time[now])
        if degree[i]==0:
            queue.append(i)

for i in range(1,n+1):
    print(result[i]+prod_time[i])
    

📖 백준 1948 (🔗백준 1948 문제)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준