하루에 한 문제
위상정렬 본문
위상정렬이란?
순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다.
다음과 같은 그래프에서 앞선 작업 2,3이 끝나야 뒤 작업 4가 이루어질 수 있다.
이 때 둘 중 무엇을 먼저 끝내던 규칙에 위배 되지 않기 때문에 경로는 여러 개가 나올 수 있음!
단 위상정렬이 성립하기 위해서는 DAG여야 한다!
DAG : Directed Acyclic Graph 사이클이 존재하지 않는 방향그래프( 사이클이 있으면 시작지점을 정할 수 없음)
위상 정렬 원리
위상 정렬을 스택이나 큐를 사용하여 구현할 수 있지만 큐를 사용하는 방법이 더 일반적이니 큐를 이용해보자
1. 진입 차수가 0인 정점을 큐에 넣는다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 삭제한다.
3. 간선 삭제 이후 진입 차수가 0이 된 정점을 큐에 넣는다.
4. 1~3반복
1. 차수가 0인 1번 노드를 큐에 삽입!
2. 1번 노드와 연결된 간선 삭제 후 진입차수가 0이된 2, 3을 큐에 삽입!
3. 2,3번 노드와 연결된 간선 삭제 후 진입차수가 0이된 4를 큐에 삽입!
3. 4번 노드와 연결된 간선 삭제 후 진입차수가 0이된 5를 큐에 삽입!
위상정렬을 통해 푼 문제의 코드가 궁금하다면!
[BOJ-1766][위상정렬] 문제집 -Java
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸..
dkwjdi.tistory.com
참고
ssungkang.tistory.com/entry/Algorithm-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC