[Algorithms] 위상 정렬 알고리즘
[Algorithms] 위상 정렬 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 위상정렬 알고리즘에 대해서 정리를 해보도록 하겠습니다. 위상 정렬 알고리즘은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해 주기 위한 알고리즘입니다.
예를들어, 회사에 입사해서 주재원가기까지의 과정이 아래의 이미지에 담겨있다고 가정하겠습니다.
방향성이 있는 그래프이고, 어떤 행위를 수행하기 위해서는 사전 조건으로 반드시 수행되어야 될 임무가 있습니다. 즉, 순서가 정해져 있어야 합니다. 회사 사이트에 가입을 하기 위해서는 사전에 회사에 입사를 해야된다는 조건이 있습니다.
위상 정렬의 흐름으로 나열을 하면 다음과 같습니다.
회사 입사 -> 정직원 되기 -> 회사 사이트 가입하기 -> SW 검정 취득 -> 대학원 서류 작성 -> 대학원 진학 -> 주재원
위와 같이 정렬을 하면, 주재원가기 까지 순서를 이어나갈 수 있습니다. 위상 정렬이 적용되기 위해서는 DAG(Directed Acyclic Grapth)에만 적용이 가능합니다. 싸이클이 발생하면 순서상으로 어디가 더 선행이 되어야 하는지를 정할 수 없기 때문에 싸이클이 생겨서는 안됩니다.
1. 위상 정렬 알고리즘 동작 방식
필자 같은 경우는, 위상정렬을 구현할 때 BFS 방식을 이용해서 구현을 했습니다. 구현을 하기위해서는 각 노드를 target으로 하는 정점의 갯수가 몇개인지를 파악 해야됩니다. 가령 1->2 와 같은 간선이 있으면, 2번 정점 입장에서는 1번으로부터 들어오는 간선 정보 +1이 생기는 것입니다.
이런식의 간선정보를 input정보로부터 받아서 업데이트를 해야됩니다.
- linecount : 1차원 배열로 해당 정점을 target으로 하는 간선이 몇개인지를 표기하는 변수입니다.
- result : 1차원 배열로 linecount를 하나씩 지워주면서 0이 되는 시점에 해당 변수에 담아 줍니다. 즉, 위상의 순서에 대한 결과입니다.
처음에는 위에서 보이는것과 같이 linecount를 1차원배열로 해서 input정보를 받아줍니다. 최초 시작점은 linecount가 0인 점점이 최상위 위상으로부터 시작이 됩니다.
BFS에 의해서 queue에다가 1번 점점을 담았다가 빼면서 연결된 인접리스트에서 7,3을 타겟으로 하고있다는것을 알고 linecount에서 -1을 해줍니다. 위의 그림과 같이 기존에 7,3을 target으로 하는 간선정보는 1개 밖에 없기 때문에 지워주면 0이 되면서, result에 담아줍니다. 여기까지는 1->7->3의 위상이 생기는 것입니다.
그런데, 위상정렬의 특징중 하나가 답이 무조건 1개가 될 수 없다는 것입니다. 인접리스트에 담긴 순서에 따라서, 1->7->3이 될수도있고, 1->3->7이 될수도 있습니다. 즉, 위상정렬에 대한 답은 여러개가 될 수 있다는 특징이 있습니다.
7,3이 현재 queue에 담겨있고, 위의 그림에서는 3을 먼저 꺼내서 다음 노드인 5에 대한 linecount를 지웠지만, 5같은 경우는 2개의 간선정보가 있었기에 0이 되지 않습니다. 그래서 아직은 result에 들어갈 수가 없는 상태입니다.
7노드를 꺼내서 다음 노드인 2정점을 간후, 간선정보를 지웠더니, 0으로 바뀌었습니다.
다시 2번 노드가 queue에 들어와있고, 꺼내서 다음 노드인 4에 대한 간선정보를 지워줍니다. 이런식으로 순차적으로 내려가면 다음과 같습니다.
2. 위상 정렬 알고리즘 소스코드
BFS방식으로 큐를 이용하여 풀이하였습니다.
