[게임개발] 위상정렬(Topological Sorting) | 백준 1516번 | python

🌟 위상정렬이란?

어떤 일을 하기 위해 일련의 작업을 차례때로 수행해야 하는 알고리즘이다.
즉, 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

 

degree

[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

 

예제 입력1

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

예제 출력1

10
20
14
18
17

 

📍풀이

위상 정렬로 건물을 짓되, 건물을 짓는 시간도 저장하고 있어야 한다.
시간 업데이트를 해줘야 하는데, 다음 건물의 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])