오늘은 깊이 우선 탐색을 공부를 해보자. 의미론적 추론 알고리즘 수정하고 개선하는 상황을 마주하게 되었는데 기본적인 알고리즘을 공부해두면 좋을 것 같아서 정리하게 되었다.
1. 개념
깊이 우선 탐색은 깊이를 우선적으로 탐색하는 알고리즘으로, 스택(Stack)을 사용해서 노드를 탐색하는 방법이다.
2. DFS 작동 순서
- 스택의 최상단 노드를 확인
- 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뺀다.
- 위의 과정을 반복한다.
- 방문 순서(경로)가 결정된다.
3. 예시
내가 해결해야 했던 문제로 예시를 들어서 정리를 해보면.. 건물에는 수많은 센서가 설치되어 있다. 물론 데이터들을 많이 수집하고 있지만 그중에서도 데이터 중에 데이터인 메타데이터를 어떻게 관리할지가 매우 중요하다. 메타데이터는 다양한 물리적 단어들로 구성되어 있어 효율적으로 관리만 할 수 있다면 고성능의 기술들을 현장에 적용할 수 있다는 큰 장점이 있다. 특히 이러한 메타데이터들을 토큰화한 후 가장 의미가 높은 노드부터 가장 낮은 단위까지 계층화된 메타데이터를 그래프화하여 아래의 DFS 같은 문제를 적용하면 간편하게 문제를 해결할 수 있을 것으로 생각된다. 왼편에는 1개의 그래프가 있고 오른편에는 1개의 스택이 있다고 생각해보자.
시작 노드(1번 노드)를 스택에 삽입하면서 알고리즘이 시작된다.(1번 노드는 방문 처리)(한가지 조심해야 할 점이 혹시 2번 또는 3번으로 넘어갈 때 우선순위가 있는지는 문제에 따라서 그 순서가 결정된다. 이 예시는 어디로 가든지 상관없다고 가정한다.)
2번 노드 스택에 삽입 및 방문처리 : 스택에 있던 최상단 노드가 1번 노드이고, 이 1번 노드의 인접한 노드 중에서 방문하지 않은 2번 노드를 처리해준다.
3번 노드 스택에 삽입 및 방문처리 : 2번 노드의 인접 노드 중에서 방문하지 않은 노드인 3번 노드를 스택에 넣는다.
6번 노드 스택에 삽입 및 방문처리 : 6번 노드는 3번 노드의 인접 노드 중에서 방문하지 않은 노드이므로 스택에 추가한다.
7번 노드 스택에 삽입 및 방문처리 : 7번 노드는 6번 노드의 인접 노드 중에서 방문하지 않은 노드이므로 방문처리한다.
3, 6, 7번 노드는 방문처리는 그대로 되어 있지만, 스택에서 빠져나온다.(인접노드가 더이상 없다.)
이후에 2번 노드의 인접노드 중에서 4번 노드에 방문하지 않았으므로 4번 노드를 스택에 넣는다.
5번 노드 스택에 삽입 및 방문처리 : 5번 노드는 4번 노드의 인접 노드 중에서 방문하지 않은 노드이므로 스택에 추가하고 방문처리 한다.(모든 노드에 방문 완료)
최종적으로는 스택에서 하나씩 노드가 빠져나와서 모두 방문이 완료되었다.
이러한 깊이를 우선적으로 탐색하는 과정을 통해 방문 경로가 결정된다.
이 과정을 그대로 건물에 적용해보면 건물-실외기1-실내기11-실내기12-실외기2-실내기21-실내기22 이런식으로도 탐색이 가능한 것으로 보인다.
참고자료
동빈나님 알고리즘 자료 항상 감사합니다.
(https://m.blog.naver.com/ndb796/221230945092)
