1005 ACM

개요

순서가 정해져있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정해주는 정렬 알고리즘.

1005 ACM 처럼 건물 건설 테크트리가 있다고 할 때, 그 테크트리가 바로 순서가 정해져있는 작업이고, 각 테크트리를 일종의 “조건”이라고 생각할 수 있다. 2를 짓기위해 1이 필요하다면 그것이 ‘조건’이다.

또 4를 짓기 위해서 2와 3 모두 필요한데, 위상 정렬에서 방향 그래프가 위 예시같이 그려진다면 두 조건 모두 만족해야한다는 뜻이다. 따라서 1005 ACM 문제는 아주 전형적인 위상 정렬 문제라고 볼 수 있다.

위상 정렬 알고리즘을 통해 두 가지를 해결할 수 있다.

1. 현재 그래프가 위상 정렬 가능한지
2. 가능하다면 그 결과가 무엇인지

<aside> ⚠️ 주의 사항 위상정렬은 DAG(Directed Acyclic Graph: 사이클이 없는 방향그래프 = 방향 비순환 그래프)에만 적용 가능하다. 시작점이 필요하기 때문.

</aside>

알고리즘 및 구현

크게 두 가지 방법이 있는데, 하나는 큐, 하나는 스택을 사용한다.

큐

1. 진입차수가 0인 정점을 큐에 삽입: 시작점을 정해줘야 한다는 얘기.
2. pop한 후, 연결된 모든 간선을 제거.
3. 간선 제거 이후 진입 차수가 0이 된 정점을 모두 큐에 삽입
4. 큐가 빌 때 까지 1~2를 반복

큐가 비었을 때,

1. 모든 정점을 방문하기 전에 큐가 빈다면 사이클이 존재하는 것.
2. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬 결과.