그래프 알고리즘 : 코드 편
D+49
한 권의 책이 계속 중구난방이 되어가는 느낌을 어쩔 수 없다. 내가 하기로 했던 것이 있는데 그것을 또 매일 쓰자니 주제가 다소 애매해지는 부분이 있다. 하지만 그래도 일단 써본다. 이번 호가 끝나면 그 후에 좀 더 분화하는 방식으로 나가야겠다. 그러면 시작해 본다.
그래프 알고리즘 : BFS
그래프는 노드와, 각 노드 간의 연결을 자료구조로 나타낸 것이다. 도로네트워크, 컴퓨터 그래픽 등에 다양하게 쓰인다. 노드와 노드의 연결을 표현하다 보니 단골로 나오는 문제들이 있다. 첫째는 주어진 그래프에서 두 노드 간 연결이 되어있는지 판별하는 것이고, 두 번째는 연결되어 있다면 가장 짧은 경로를 찾는 것이다. 두 노드 간 연결성을 찾기 위해 사용되는 여러 알고리즘 중 Breadth First Search(이하 BFS)가 있다. 한국말로는 너비우선 탐색이라고도 부른다.
BFS와 Level Set
하나의 노드를 u0라고 한다면, 해당 노드로부터 거리 1로 다다르는 노드의 집합을 L_u1, 거리 2만큼 다다르는 노드의 집합을 L_u2라고 표현할 수 있다. 여기서 알 수 있는 것인 L_u(i)와 L_u(i+1)에 속하는 노드 중 서로 연결되어 있다면 그 둘은 거리 1만큼 떨어져 있으며, 가장 짧은 거리를 가진다. 가장 짧은 거리의 합이 최종적으로 최단거리를 나타내기 때문에 시작 노드에서부터 타깃 노드까지 사이의 Level Set 중 연결된 Path가 있으면 이를 최단거리로 구할 수 있다.
가령 위 그림의 노드 0을 기준으로 level set을 표시해 보면 아래 그림과 같다.
보통 List로 표현하기 때문에 list로 표현하면 아래와 같다
[
[0],
[1,3,4],
[2]
]
Level Set을 통해 우리가 알고자 하는 것은 서로 간의 위계이다. 위 Level Set과, Adjacency List를 이용하면, 각 노드의 Parent를 구할 수 있다. 여기서 Parent란 각 노드가 시작 노드 방향(여기서는 노드 0)을 기준으로 자기 자신이 속한 Level Set에서 자신보다 시작 노드에 가까운 Level Set에 있는 연결된 노드를 뜻한다. 무슨 말이냐 그림으로 살펴보자.
노드 0을 시작노드로 했을 때 각 노드의 parent를 그려보면 위와 같다. 노드 0은 자기 자신을 parent로 표시하고, 나머지 노드는 Level Set에 따라 parent를 표시하게 된다. 여기까지 그려보면 거의 답은 다 나왔다. 이제 원하는 끝 노드만 설정하면 parent를 계산해 가장 짧은 거리를 구할 수 있다.
이제 MIT 식 코드
코드르 볼 때마다 어쩜 이렇게 간결하게 쓰는지 놀라울 따름이다. 교육자료에 있는 내용이지만 옮겨 썼다. 참고로 brunch에서는 코드를 옮겨 쓰기가 불편해 캡처로 대체하는 점 양해 바란다. 그리고 시각화를 위해 코드를 추가했다.
BFS의 경우 위와 같이 구성되어 있다. 노드의 개수만큼 parent를 만든 후, 시작노드의 parent는 자기 자신으로 초기화한다. 또한 level set 간의 관계를 이용해 parent를 구하는 만큼, levelset을 자기 자신을 넣어 정의한다.
그 후 while 반복문은 다음과 같다. 첫째로 level에 비어있는 set을 하나 넣는다. 그 후 이전 level set의 모든 노드(u)에 대해, 인접한 노드(v)를 구한다. 인접노드(v)의 parent가 없다면, 인접노드(v)의 parent는 u로 설정한다. 그리고 비어있는 level set에 v를 넣는다. 여기에서 parent가 없을 시에만 구문을 작동하는 이유는 다음과 같다. 우선 graph이기 때문에 하나의 노드가 다른 노드로부터 여러 번 연결되어 있을 수 있다. 그리고 이미 parent가 있다는 것은 더 가까운 levelset으로부터 연결되었다는 뜻이기 때문에 뒤에 발생한 level set에서는 작업을 진행할 필요가 없다. 이제 parent만 구해지면 최단 거리는 문제없다.
위 구문을 해설해 보자.
첫째로 BFS를 이용해 parent를 구한다. 여기서 직관적으로 이해가 잘 안 가지만 하나 짚고 넘어가야 하는 부분이 있다. 멀리 있는 노드로부터, 시작 노드를 구하는 방식으로 코드가 구성되어 있다는 점이다. 따라서 parent [t]가 None인지 아닌지를 판별한 후 코드를 진행하게 된다.
그 후 현재 노드를 t를 i에 할당해 현재 노드로 설정하고, path도 t를 시작으로 초기화한다. 그 후에는 i가 s가 될 때까지 parent를 탐색하는 방식으로 코드가 구성되어 있다. 마지막의 [::-1]은 시작 노드를 기준으로 순서를 바꾸기 위함이다.
깃허브 주소
https://github.com/Chaeguevara/playGround/blob/main/algorithm/6006/Lec9/graph.py
혹시나 필요하신 분들을 위해 코드를 첨부한다.
