위상정렬(Topological Sort)

• DAG(Directed Acyclic Graph)
  : 사이클이 없는 방향 있는 그래프

• 위상 정렬(Topological Sort)
  : 그래프의 간선 u → v에서 v를 선행하기에 앞서 u를 먼저 수행해야 한다는 의미에서 봤을 때 정점의 순서를 찾아주는 알고리즘
  : 보통 위상정렬의 결과는 여러가지가 있다. (DOF == 0을 만족하는 node간에는 우선 순위가 없기 때문)

• 방법론
  : 구현에는 BFS를 이용하는 방법과 DFS를 이용하는 방법이 있다.
  : in-degree가 0인 node를 해당 순서(보통은 queue)에 추가하면서 해결
  : 인접행렬의 경우는 간선을 지우는 것은 해당 행열의 값을 0으로 바꾸면 쉬운 일이지만, 인접리스트에서는 해줘야 할 일이 많고 복잡하다. 따라서, 실제로 인접리스트의 간선을 지우지 않고, in-degree만 관리하면 된다.
  : 사이클이 있는 그래프에서는 처음 지점을 뽑을 수 없기 때문에 수행이 불가능하다.

• BFS 방법 구현
  : BFS와 유사하게 구현할 수 있다. 다만, BFS에서는 방문하지 않은 노드를 queue에 추가하면서 진행해 나가는 반면, 방문하지 않는 점과 동시에 in-degree가 0이 되었는지를 추가해야 한다.
  : BFS의 시간 복잡도인 O(V+E)인데 V는 queue에 들어왔다 나갔다하는 방법 간선(E)는 한번씩 순회하기 때문에 O(E)와 같다.

• DFS 방법 구현
  : DFS에서는 그래프의 간선을 모두 뒤집어 놓고 DFS를 수행하고, 정점이 스택에서 빠져나오는 순서를 기록하면 위상 정렬의 순서와 같아지게 된다.

백준 1948 문제

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

n = int(rdln())
m = int(rdln())

ind = [0] * (n+1) # in-degree1
ind2 = [0] * (n+1) # in-degree2
d = [0] * (n+1)
check = [False] * (n+1) # 방문했는지 확인하는 배열
graph = [[] for _ in range(1, n+1)] # graph1
graph2 = [[] for _ in range(1, n+1)] # graph2
for _ in range(m):
    st, en, co = map(int, rdln().split())
    graph[st].append((en, co))
    graph2[en].append((st, co))
    ind[en] += 1
    ind2[st] += 1

start, end = map(int, rdln().split())
queue = deque()
for i in range(1, n+1):
    if ind[i] == 0:
        queue.append(i)

while queue:
    x = queue.popleft()
    for _en, _co in graph[x]:
        d[_en] = max(d[_en], d[x] + _co) # 최대 distance구하기
        ind[_en] -= 1 # _en node 1 degree 줄이기
        if ind[_en] == 0:
            queue.append(_en)

sys.stdout.write(f"{d[end]}\n")

ans = 0
check[end] = True
for i in range(1, n+1):
    if ind2[i] == 0:
        queue.append(i)

while queue:
    x = queue.popleft()
    for _st, _co in graph2[x]:
        if check[x] and (d[x] - d[_st] == _co): # x 노드에서 _st 비용 차이가 _co면 해당 노드 check[_st] = True
            check[_st] = True 
            ans += 1
        ind2[_st] -= 1
        if ind2[_st] == 0:
            queue.append(_st)

sys.stdout.write(f"{ans}\n")