위상정렬이란?

어떤 일을 하기 위해 일련의 작업을 차례때로 수행해야 하는 알고리즘이다.
즉, B를 하기 위해선 A를 해야하고, C를 하기 위해선 B를 해야하는 상황에서 A-> B-> C 순서로 할 수 있다.

예를 들어, 대학교에서 선수 과목을 들어야 해당 과목을 들을 수 있듯이 순서가 정해져 있는 알고리즘이다.

N(노드의 개수) = 5, M(간선의 개수) = 5 인 다음과 같은 그래프에서 위상정렬을 수행해보자.

이 알고리즘을 해결하기 위해서는 3가지를 고려해야 한다.

• indegree
• queue
• graph

indegree

각 노드에서 진입 차수 개수를 저장

graph

노드의 인접 리스트로 그래프 구현

queue

1. popleft()해서 나온 노드의 영향이 있는 graph으로
2. 나온 노드를 indegree-=1
3. indegree 진입차수가 0이면 queue에 append() 한다.

indegree

[1]	[2]	[3]	[4]	[5]
0	1	1	2	1

graph

[1]	[2]	[3]	[4]	[5]
[2,3,4]		[4,5]

1. 노드 1부터 시작

queue

[0]
1

(1) queue.popleft() 하면 1이 나오므로,
(2) graph의 index 1에 있는 [2,3,4]에 해당하는 indegree에서 -1를 해준다.

indegree

[1]	[2]	[3]	[4]	[5]
0	0	0	1	1

(3) indegree [2,3,4] 중에서 진입차수가 0이면 queue에 넣는다.
‼️ 4는 0이 아니므로 생략 !!
queue

[0]	[1]
2	3

2. 다음은 2

(1) queue.popleft() 하면 2이 나오므로,
(2) graph의 index 2에는 아무것도 없으니 생략.
indegree

[1]	[2]	[3]	[4]	[5]
0	0	0	1	1

queue

[0]
3

3. 다음은 3

(1) queue.popleft() 하면 3이 나오므로,
(2) graph의 index 1에 있는 [4,5]에 해당하는 indegree에서 -1를 해준다.
indegree

[1]	[2]	[3]	[4]	[5]
0	0	0	0	0

(3) indegree [2,3,4] 중에서 진입차수가 0이면 queue에 넣는다.
queue

[0]	[1]
4	5

이후.. 똑같아요!

---

게임 개발하기

백준 1516번

https://www.acmicpc.net/problem/1516

풀이
위상 정렬로 건물을 짓되, 건물을 짓는 시간도 저장하고 있어야 한다.
시간 업데이트를 해줘야 하는데, 다음 건물의 result에 있는 값과 지금 건물의 result값과 지금 건물의 짓는 시간을 더한 값과 비교를 해서 더 큰 것을 저장한다.

코드

# 위상 정렬
from collections import deque

N = int(input())

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

for i in range(1, N + 1):
    inputList = list(map(int, input().split(' ')))[:-1]
    cost[i] = inputList[0]

    for j in range(1, len(inputList)):
        building[inputList[j]].append(i)
        indegree[i] += 1

# print(building)
# print(cost)
# print(indegree)

queue = deque()

for i in range(1, N + 1):
    if indegree[i] == 0:  # 제약이 없으면
        queue.append(i)

result = [0] * (N + 1)

while queue:
    now = queue.popleft()

    for next in building[now]:
        indegree[next] -= 1
        # 시간 업데이트
        result[next] = max(result[next], result[now] + cost[now])
        if indegree[next] == 0:
            queue.append(next)

# print("result", result)
for i in range(1, N + 1):
    print(result[i] + cost[i])