위상 정렬

• 위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
• 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

✅ 위상 정렬의 핵심 이론

➡️ 위상 정렬의 원리 이해하기

1. 진입 차수를 이해해보기. 진입 차수는 자기 자신을 가리키는 에지의 개수이다. 다음을 보면 ArrayList(인접리스트)로 그래프를 표현했다. 그래프는 사이클이 없는 상태이다.

   

진입 차수 배열 D를 다음과 같이 업데이트 한다. 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가시키는 그림과 함께 다음의 결과 배열을 확인하자

1. 진입 차수 배열에서 **진입 차수가 0인 노드를 선택(자신을 가리키는 노드가 없으므로 순서가 첫번째 일것)**하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺸다. (즉, 1이 가리키는 2, 3의 진입차수의 값을 1씩 감소시킨다.)

위 그림의 경우 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만드는 것이다. 계속해서 다음 노드 2를 선택하여 반복한다. 이 과정은 모든 노드가 정렬될 때까지 반복한다. 여기서 진입 차수가 0인 노드를 3을 먼저 선택했다면 3이 우선 위상 정렬 배열에 들어갈 것이다. 앞서 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다고 말했던 것이 이런 경우이다.

위상 정렬 배열 결과는 다음과 같다.

📄 예시 코드 (백준 2252번)

줄 세우기