위상 정렬
의미
- 방향이 존재하는 유향 그래프 내에서, 방향을 거스르지 않으면서 순서를 부여해서 탐색(방문)하는 방법
조건 및 특징
- 유향 그래프
- Cycle이 존재하면 안된다. => cycle 판단도 동시에 가능하다는 말과도 같다
- 관계성이 있는 그룹 내에서만 순서를 지키면 된다. => 때문에 여러 순서 결과가 도출되는 경우가 많다.
위상 정렬의 목적
문제 예시
BFS를 이용한 구현
1. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
- 차수 : 정점에 연결된 간선 수
- 진입차수, 진출차수 : 유향 그래프에서의 차수를 방향을 기준으로 구분
2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
- 인접한 노드의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
4. 큐가 공백 큐 상태가 될 때까지 2~3 작업을 반복한다.
- 모든 노드가 처리되지 않았다면 Cycle이 발생했다는 의미.
참고 코드
public class TopologySortTest {
// static 영역
// Node 클래스를 이용하여 인접 리스트 만들기
// Node 클래스는 int vertex(다음 노드 번호)와 Node link(이전 노드의 정보)를 필드로 한다.
static class Node {
int vertex;
Node link;
public Node(int vertex, Node link) {
this.vertex = vertex;
this.link = link;
}
}
static int N,M;
// Node[] adjList 를 선언
// 이는 입력을 받을때 from, to를 이용하여 만듬
static Node[] adjList;
// 진입차수 관리 배열 선언(int[] inDegree)
// 입력받을때 inDegree[to]++;
static int[] inDegree;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
adjList = new Node[N+1]; // 1번부터 시작
inDegree = new int[N+1]; // adjList 와 같은 길이의 배열로 선언
int from, to;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
adjList[from] = new Node(to, adjList[from]);
inDegree[to]++; // 간선을 받는 대상의 인접 차수 증가
}
ArrayList<Integer> list = topologySort();
if(list.size() == N) {
//위상 정렬 완성(cycle이 없음)
for (Integer vertex: list){
System.out.print(vertex + " ");
}
System.out.println();
}
else {
//cycle이 존재
System.out.println("cycle");
}
}
//정렬된 결과를 List로 반환
static ArrayList<Integer> topologySort(){
// 반환할 순서를 담을 리스트
ArrayList<Integer> result = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i < N+1; i++) {
// 인접(진입) 차수가 0이면 해당 vertex(to)를 queue 에 제공
if(inDegree[i] == 0) queue.offer(i);
}
//queue 가 빌 때까지 작업
while(!queue.isEmpty()){
int current = queue.poll(); // to의 값이 꺼내짐
result.add(current);
//현재 정점 기준으로 인접정점 처리(간선 제거)
//시작: 현재 vertex 의 노드 정보, 종료: null, 다음: 조회된 노드(temp)에 연결된 노드(link)
for (Node temp = adjList[current]; temp != null; temp = temp.link){
inDegree[temp.vertex]--; //현재 조회된 노드의 다음 노드의 진입 차수
if(inDegree[temp.vertex] == 0){ //다음 노드 진입 차수를 1 감소시켰을때, 0이면 queue 넣음
queue.offer(temp.vertex);
}
}
}
//cycle이 없다면, 모든 정점이 들어있는 list 반환
//cycle이 있었다면, cycle 때문에 못 들어간 정점을 제외한 list 반환
return result;
}
}
참고 코드2; 내가 더 편한 코드
- 백준2056 작업 코드로 참고
- 나는 인접 리스트를 선행->후행 관계의 리스트로 만드는 것을 좀 더 선호한다. 이유는 나한테는 그게 직관적으로 느껴지기 때문
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class JUN2056_작업 {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int N; // 수행할 작업 개수
static ArrayList<Integer>[] adjList; // 선행, 후행 관계를 갖는 리스트 배열: 배열 인덱스를 선행(from), 해당 인덱스의 리스트 값을 후행(to)으로 넣는 것이 포인트
static int[] inDegree; // 각 정점의 인접 차수를 저장하는 배열: 배열 인덱스를 to값으로 설정
static int[] time; // 각 작업의 시간을 저장할 배열; 해당 문제의 추가 옵션, 위상 정렬을 실시하면 다양한 경우의 수가 나올 수 있기 때문에 이러한 특정 조건을 주어 하나의 답을 도출하도록 유도한다.
public static void main(String[] args) throws IOException {
N = Integer.parseInt(bf.readLine());
adjList = new ArrayList[N+1];
inDegree = new int[N+1];
time = new int[N+1];
int amount, from;
for (int i = 1; i < N+1; i++) {
adjList[i] = new ArrayList<>();
st= new StringTokenizer(bf.readLine());
time[i] = Integer.parseInt(st.nextToken());
amount = Integer.parseInt(st.nextToken());
if(amount != 0){
for (int j = 0; j < amount; j++) {
from = Integer.parseInt(st.nextToken());
adjList[from].add(i);
inDegree[i]++;
}
}
}
// 위상 정렬 실시
System.out.println(topologySort());
}
private static int topologySort() {
int[] result = new int[N+1];
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i < N+1; i++) {
result[i] = time[i];
// 인접(진입) 차수가 0이면 해당 vertex(to)를 queue 에 제공
if(inDegree[i] == 0) queue.offer(i);
}
//queue 가 빌 때까지 작업
while(!queue.isEmpty()){
int current = queue.poll(); // to의 값이 꺼내짐
for (int next : adjList[current]){
result[next] = Math.max(result[next], (time[next] + result[current]));
inDegree[next]--; //현재 조회된 노드의 다음 노드의 진입 차수
if(inDegree[next] == 0){ //다음 노드 진입 차수를 1 감소시켰을때, 0이면 queue 넣음
queue.offer(next);
}
}
}
int max = 0;
for (int i = 1; i < N+1; i++) {
max = Math.max(max,result[i]);
}
return max;
}
}