데이터 과학 유망주의 매일 글쓰기 — 스물 세번째 일요일
Graph에서의 BFS
# Graph, # BFS
오늘 한일:
어제까지 계속 피타고라스 정리에 기반한 유클리드 거리(Euclidean Distance)라는 개념을 활용하여 문제를 풀고자 했으나, 실패했다. 결국, 다른 선택지가 없었던 나는 Graph에서의 BFS를 활용할 수 밖에 없다고 판단했다.
일단 미로가 Matrix형태로 주어졌지만, 노드끼리 서로이어지고, 대칭관계인 인접행렬(Adjacent Matrix)가 아니었다. 그래서, 미로를 Dictionary형태로 각 노드들의 위치 사이에 연결관계를 나타내는 인접리스트(Adjacent List)로 변형해 주어야겠다는 생각이들었다.
그렇게 한 후에는, BFS를 활용하여 출발지에서 목적지까지 가장 빠른 길을 찾아야한다. 그렇다면, 어떻게 무작위로 선출된 두 지점 사이에서, 가장 빠른 지름길을 찾아낼 수 있을까?
Graph에서의 BFS
위 그림과 같은 이진그래프(Binary Graph)를 가정한다. 알다시피 노드와 Edge로 그래프는 구분되어 있는데, 이진그래프(Binary Graph)에서는 “1”이 연결되어있음을 나타내고 “0”은 연결관계가 없음을 나타낸다. 그러므로, 연결되어있는 노드들 사이에는 Edge가 존재한다고 볼 수 있다. 위 그래프의 지정된 시작점(Source)인 “0”번 노드에서 목적지(Destination)인 “7”번 노드까지갈 수 있는 가장 빠른 길은 어떻게 찾을 수 있을까?
그림에서보면, 0에서 7까지 가는 가장 빠른 길은 노드 “3”만 거쳐서 가는 것이다. 그러므로 가장 빠른 길은 0 -> 3 -> 7이 된다. 즉, 이 3개의 노드 사이에 존재하는 Edge는 2개이므로, 답은 “2”가 되어야한다.
또다른 예로, 2번 노드에서 6번 노드까지가는 가장 빠른 길을 탐색한다면, 아래 2가지 경우가 있을 수 있다.
- 2 -> 1 -> 0 -> 3 -> 4 -> 6
- 2 -> 1 -> 0 -> 3 -> 7-> 6
위 두 가지 경우 모두 시작점과 도착점 사이에 존재하는 Edge는 5개이기 때문에, 답은 “5”가 되어야한다.
방법
위 그래프에서 가장 빠른 길을 탐색하는 가장 좋은 방법은, 가장 빠른 길을 먼저 찾으려는 너비우선검색(BFS)를 활용하는 것이다. BFS는 주어진 노드들 사이에서 이전 탐색 Vertice를 계속 저장하면서 탐색을 해 나가기 때문에, Queue를 사용한다는 특징이 있다. 이 알고리즘은 그래프에서 더 큰 노드에서 더 작은 노드로 갈 때에도 사용될 수 있다.
- 먼저, Edge로 이루어진 거리 정보를 저장하기 위한 배열 (dist[0 ~ v-1])과 이전 시점의 노드 정보를 저장하기 위한 배열(pred[0 ~ v-1])을 초기화한다.
- dist 배열은 각 노드를 방문할 때마다 시작 노드에서 현재 노드가 얼마나 먼지를 측정하고 저장한다.
- 이전 시점의 노드를 pred 배열에 저장한다.
- dist 배열이 시작점으로부터 각 노드가 얼마나 먼지에 대한 정보를 담게되며, pred 배열을 통해 시작점으로 부터 각 노드와의 연결 상태를 알 수 있게 된다.
의사코드
initialize dist array of size (v)
initialize pred array of size (v)for i in range of (start, graph):
save (i - start) to dist array
save (graph[(i - start)-1]) to pred array
시간복잡도
dist 배열을 통해 상수시간(O(1))만으로 시작점과 각 노드 사이의 거리 정보를 알 수 있으며, pred 배열을 통해 시작점과 각 노드사이의 연결 상태를 알아내는데는 최악으로 따져도 선형시간(O(V))이 걸린다. V는 배열 pred의 크기로 볼 수 있다.
결국, 그 어떤 시작점과 도착점이 주어지더라도, 연산에 걸리는 시간은 상수시간(O(V+E))이 되는 것이다. 만약 위 그래프가 이진그래프가 아닌, 각 노드의 연결거리가 다른 가중치그래프(Weighted Graph)라면, 로그시간(O(E+VLogV))이 될 것이다. 여기서 “V”는 노드, “E”는 Edge를 말한다.
앞으로 할일:
오늘은 Graph의 BFS에 대해 리뷰해 보았다. 그 중에서도 가중치가 없이 순수한 연결상태와 비연결상태만을 나타내는 이진그래프에서 탐구를 해 보았다. 이 것을 코드로 구현하기 위해서는 각 노드들 사이의 연결상태를 나타내는 인접리스트로 주어진 매트리스를 변형해야 하는데, 그 작업이 지금 쉽게 되지 않고 있어서, 오늘 역시 의사코드까지만 올릴 수 밖에 없었다. 내가 이 문제를 해결하게 되면 업데이트해서, 실제 구현한 코드까지 공유하고싶다.
이 세상에 정말 쉬운게 하나도 없다. 나이가 들어가면서 더 절실히 느끼는 것 같다. 그렇지만, 계속 매일 밤을 늦게까지 코드를 붙잡으면서도, 진전이 별로 없으면 침대로 발을 옮기기 쉽지 않다. 그 정도로 재미있는것 또한 사실이다. 쉬운게 별로 없지만, 그래도 재미있기에 끈기를 가지고 하게되는 것이다.
프로그래밍을 하면서, 어려운 것에 도전한다는 것이 매우 보람있고 흥미있는 일이 될 수 있다는 것을 깨닫게된다. 뭐에 막히면 쉽게 포기하던 과거의 나를 반성하기도 한다. 끈기를 기르면서, 진정한 기쁨은 쉬운 것을 단번에 성취하기보다, 어려운 것을 힘겹게 해결했을 때 훨씬 크게 온다는 것도 알게되었다.
오늘을 포함에 문제 해결에 2일 정도가 남았다. 그동안 최대한 내가 할 수 있는 모든 것들을 해보자. 혹여나 문제를 완벽하게 해결하지 못하더라도, 내가 지난 일주일 동안 고생한 모든 과정이 의미가 없지는 않았다고 생각한다. 기존 BFS가 아닌 다른 방법으로 나름 창의적인 해결책을 모색해보려했고, 거기서 추론해낸 나의 논리와 아이디어는 앞으로도 내가 다른 문제에 도전함에 있어서도 생각의 틀을 넓히는 힘이 될 것이다.
때때로, 인간은 죽음의 문턱을 넘을 때마다 더 강해지는 드래곤볼의 초사이어인들과 다르지 않다는 생각이든다. 뇌가 부셔질 것 같은 고통을 겪어도, 정말 이제는 안될 것 같은 상황에서도, 조금 더 나아가면 놀라울 정도로 많은 성장을 하는 것이 인간이다. 이 사실이 진리라고 믿고, 나는 매일 더 나아갈 것이다. 내 뇌가 힘든 과정을 계속 겪을수록, 나는 전보다 훨씬 더 똑똑한 인간으로 진화할테니까.
참조:
(1) https://www.geeksforgeeks.org/shortest-path-unweighted-graph/
