위상정렬
위상정렬을 간단하게 요약하면
'방향그래프의 정점 처리 순서를 선형으로 정렬하는 방법'이라고 할 수 있겠다.
알고리즘 문제로 말하면 특정 업무를 해야 다음 업무를 하는데 가능한 일의 처리 순서를 나타낸다거나 뭐 그런 문제에 적용할 수 있는 그런 알고리즘이다.
일단 하려면 방향그래프여야하고,
사이클(특정 노드에서 다시 그 노드로 돌아오는 경로가 있는)이 없어야한다.
대충 이런 방향 그래프가 있다면
이런 모양으로 나타낸다고 생각하면 된다.
일단 저 그래프의 간선이 start, end 구조로 입력이 들어온다고 보면,
''' 시작노드 종료노드
1 2
1 3
2 5
3 4
3 5
4 6
5 6
'''입력을 받으면서 각 노드마다 직전에 몇 개의 노드를 처리해야하는지 in_order라는 배열에 저장해주자. + 해시를 이용해 그래프 구조도 같이 만들어주자.
in_order = [0] * 7
graph = defaultdict(list)
for _ in range(7):
start, end = map(int, input().split())
graph[start].append(end)
in_order[end] += 1in_order에 대해 그림으로 간단히 표현하면
이렇게 된달까.
아무튼 배열엔
in_order = [0, 0, 1, 1, 1, 2, 2] 가 저장된다.
0번 인덱스는 무시하고, 1번 인덱스부터 순회하면서 in_order[index]의 값이 0인 값들을 큐에 넣어주자.
q = deque()
for i in range(1, 7):
if in_order[i] == 0:
q.append(i)in_order[index]의 값이 0이라는 건 이전에 처리할 노드가 없다는 뜻이니까,
즉, 시작 노드를 나타낸다(그림에서는 1번 노드).
그리고 q에서 하나씩 빼면서 그 노드를 처리하고, 연결된 노드들의 in_order의 값을 1씩 내려준다.
while q:
node = q.popleft()
visited.append(node)
for next in graph[node]:
in_order[next] -= 1
if in_order[next] == 0:
q.append(next)그리고 그 노드의 in_order값이 0이 됐다면 큐에 추가한다.
첫 번째 과정만 표현하면,
1번에서 시작해서 1 > 3 간선과 1 > 2 간선을 처리하고,
in_order[2], in_order[3]의 값을 1씩 빼준다.
빼주고 그 값이 0이 됐다면, q에 추가한다.
이 방법으로 큐가 빌 때까지 진행하면,
print(*visited)
# 1 2 3 4 5 6가 된다.
뭐 이런 식으로 처리하는 방법도 있고,
여러 알고리즘 문제 보다보면, 가능한 숫자가 낮은 노드부터 처리하는 경우도 있고,
가중치 있는 방향 그래프를 처리해야할 때도 있다.
쓰기 편해서 큐를 쓰긴 했지만,
가능한 낮은 숫자부터 처리하려면,
큐에 무언가 삽입됐을 때, 큐를 계속 정렬해주는 방법도 있을 거고,
힙을 사용하는 방법도 있을 거다. 뭐 방법이야 많으니까.
가중치가 있을 때는,
한 번에 한가지만 처리할 수 있을 때, 여러가지를 동시에 처리할 수 있을 때 등등
각 노드마다 이전까지 처리한 시간을 저장해두고 다음 노드를 처리하는데 걸리는 시간을
min 등을 이용하여 갱신하거나 뭐 DFS랑 비슷한 느낌으로도 갈 수 있겠다.
간단하게 풀어볼 수 있는 문제들은 solved class 5에 있는 문제들 중에 조금 있다.
사실 간단한 구현이면 해결되는데 의외로 백준 티어는 높은..(?) 편이다(둘 다 gold2).
이 정도도 풀어볼만 한 거 같다.
스웨아는 백준보단 채점기준이 까다롭진 않아서 다른 방법도 많이 생각해볼 수 있다.
처음엔 위상정렬 모르고 무지성으로 하긴 했는데 다 되긴 되는 느낌이랄까.
끝!
