1. 위상정렬이란?
설명에 들어가기 앞서 링크된 블로그를 읽어 보시길 추천합니다
1. 위상 정렬 설명 블로그
2. 위상 정렬 설명 블로그
위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘 이다.
예를 들어, 선행 스킬, 줄 세우기 등 방향 그래프를 이용하여 순서대로 정렬하는 것이라 생각하면 괜찮을 거 같다. 코딩 테스트에서 간간히 나오는 유형이라 무시하고 넘어갈 순 없다.
2. 예시를 통한 설명
예시는 백준의 14567. 선수 과목 (Prerequsite) 로 설명하겠습니다.
2-1. 전처리
위상정렬을 진행하기 전에 전처리 과정으로 노드끼리 연결된 것을 표현해야 한다.
전처리 과정을 거친 후, 예제 1을 표현하면 아래와 같다.
✔ 필자는 인접 리스트를 이용해서 표현하였다.
2-2. 위상정렬
전처리 과정을 다 거쳤으니 본격적으로 위상정렬을 진행하자. 위상정렬을 진행하기 위해서 두 가지가 필요하다.
- 현재 노드에 진입 간선(indegree)의 수를 저장하는 배열
- 진입 차수가 0인 노드를 저장하고 있는 큐
위의 degree 배열의 값 0이 뜻하는 바는 현재 노드에 진입 간선이 없다는 의미이다. 이는 현재 노드가 무언가를 하기 위해 앞서 무언인가를 할 필요가 없다는 의미 이다. ex) 연계 스킬을 쓰기 전에 맨 처음에 쓰는 스킬이라 생각하자.
따라서, 1번 과목을 배우기 위해서는 1학기가 필요하여 큐에는 현재 노드에 진입 간선이 0인 노드 1를 집어 넣으면 된다
큐에서 값을 빼면 현재 노드는 1이다. 현재 노드 1는 노드 2와 연결돼 있다.
⁕ 노드 2가 수행하려면 반드시 노드 1이 수행되어야 한다는 의미이다.
노드 1을 지우면서 노드 1이 가르키는 간선도 같이 없앤다.
노드 1과 간선을 지운다는 의미는 개념상의 의미이다. 따라서, 실제로 지운게 아니라 노드 1과 연결된 노드 2의 degree값 -1 을 진행한다.
마찬가지로 큐에는 진입 차수가 0인 노드 2를 넣으면 된다.
거의 다 왔다. 마지막 과정을 살펴보자.
큐에서 뺀 값 노드 2와 연결된 노드를 살펴보면 노드 3과 연결된 것을 확인할 수 있다. 위에서 진행한 방법대로 진행하면 아래와 같은 그림을 볼 수 있다.
큐에 노드 3이 들어있다. 하지만, 값을 빼봤자 노드 3과 연결된 노드가 없기 때문에 아무런 동작없이 종료한다. 따라서, 최종적으로 얻은 결과는 아래와 같다.
예제 입력 2 도 살펴보자.
전처리 과정도 거쳤고 각각 노드에 맞는 indegree 개수도 구하였고 indegree가 0인 값들도 큐에 넣었다.
진행 과정은 아래와 같은 순서대로 진행된다.
-
큐에서 노드 1을 꺼낸 모습
-
큐에서 노드 4를 꺼낸 모습
-
큐에서 노드 3를 꺼낸 모습
-
큐에서 노드 2를 꺼낸 모습
-
큐에서 노드 5를 꺼낸 모습
2-3. 마무리
위의 동작을 글로 표현하면 아래와 같다.
- 노드와 노드가 서로 연결됨을 표현하기 위해 전처리 과정을 거친다.
- 전처리를 이용하여 각각의 노드의 진입 차수를 구한다.
- 진입 차수가 0인 노드들을 큐에 넣는다.
3-1. 큐에서 값을 가져와 현재 값과 연결된 노드들의 degree-1를 한다.
3-2. 3-1 과정을 거친 후, degree 값이 0이면 큐에 넣는다.
