by
Oct 31. 2020
C++ 위상정렬
백준 줄 세우기
앞에서 깊이 우선 탐색에 대해 파이썬과 C++을 이용해 코드로 구현해보았다. 깊이 우선 탐색은 자식 노드가 없을 때까지 가능한 멀리까지 탐색한 뒤 해를 구하는 알고리즘이다. 복습하자면 이 알고리즘은 stack을 사용하고 너비 우선 탐색과 달리 현 경로상의 노드들만 기억하므로 저장공간이 적게 사용된다. 해가 깊은 단계에 있을 경우 해를 빨리 구할 수 있으나 해가 없는 경우에도 깊이 빠질 수 있다. 일단 해를 찾기만 하면 되므로 최단경로를 보장하지 않는다.
단순한 깊이 우선 탐색은 현실에서는 자주 쓰이지는 않는다. 명확한 해답이 있으면 최고이지만 없을 수도 있지 않은가? 이때 깊이 우선 탐색과 비슷한 위상 정렬은 현실에서 자주 사용되는 알고리즘이다. 대표적인 예로 게임에서 스킬 트리를 찍어보았는가?
분명 스킬 별로 단계가 존재하지만 서로 관계없는 스킬도 있을 수 있다. B스킬을 배우기 위해 A 스킬을 선행해야 하지만 C스킬을 관계없다고 표현할 수 있다. 이때 스킬을 모두 찍는 방법은 B -> A -> C, C -> B -> A, B -> C -> A가 있을 수 있다. C는 아무 때나 찍어도 되지만 적어도 B보다 A를 나중에 찍어야 된다.
또 다른 예로 대학교 전공과목으로 예를 들어보자
운영체제 수업을 배우기 위해선 시스템 프로그래밍, 자료구조, 어셈블리, 컴퓨터공학 입문 과목을 선행해야 한다. 이때 논리회로 과목은 아무 때나 배워도 상관없다.
이처럼 비교를 해서 정렬하고자 할 때 비교할 수 없는 경우도 있으므로 한 가지의 정답만 있는 게 아니라 여러 가지 방법의 해가 나올 수 있다. 이렇게 사이클은 없지만 방향이 있는 그래프를 DAG(Directed Acyclic Graph)라 하며 이 그래프를 정렬하는 알고리즘을 위상 정렬이라고 한다.
알고리즘은 DFS와 매우 유사한데 자식 노드를 방문할 때마다 방문한 순서를 노드마다 기록한다. 그리고 노드마다 깊이 우선 탐색을 하는데 마치고 나면 지금까지 방문한 횟수를 기록해둔다. 깊이 우선 탐색을 모두 마친 순서로 정렬하면 위상 정렬을 하게 된다.
예를 들어 아래와 같은 그래프가 있을 때 위상 정렬을 해보자!
1에서 3을 방문하고 3에서 4로 방문한다. 4번 노드는 자식 노드가 없으므로 최종 방문을 표시한다.
다시 3으로 돌아가니 더 이상 자식 노드가 없으므로 최종 방문 표시를 한다.
다시 1로 돌아가 2번 노드를 방문한다. 3번 노드에서 4번 노드를 방문하려고 했으나 이미 방문했으므로 방문하지 않는다. 더 이상 방문할 노드가 없으므로 최종 방문 표시를 한다.
다시 1로 돌아가니 더 이상 방문할 자식 노드가 없으므로 최종 방문 표시를 한다.
최종 방문 표시를 한 값으로 정렬을 하니
1(8) -> 2(7) -> 3(5) -> 4(4)가 된다.
만약 1에서 3이 아닌 2부터 방문했다면 순서가 1->3->2->4가 되었을 것이다.
이제 백준에서 위상 정렬을 해결하는 코드를 구현해보자
https://www.acmicpc.net/problem/2252
