JavaScript로 트리, BFS, DFS 구현하기
트리, 개념은 어렵지 않지만 실제로 알고리즘 문제를 풀 때, 트리를 사용해야 할 경우가 오면 감이 안잡힌다. 도대체 어디서부터 접근해야 트리를 사용해서 문제해결을 할 수 있을까? 더군다나 밑에서 구현 할 너비우선, 깊이우선 탐색 알고리즘을 사용해서 문제를 해결한다고? 도대체 어떻게?
일단, 원리와 구현에 대한 정확한 이해가 필요하다 싶어서, 인터넷에 넘쳐나는 훌륭한 참고자료들을 뒤로하고서 나만의 예를 포함한 글로 기록 해 놓으려고 한다.
References
- Udemy JS Algorithms Course
- Tree wikipedia Eng
- Breadth Frist Search wikipedia Eng
- Depth First Search wikipedia Eng
트리
기본개념
트리는 계층이 존재한다. 그래서 어렵다. 왜냐하면 우리는 보통 선형적으로 사고하고 행동한다. 원인과 결과, 과거와 현재 그리고 미래 등. 마치 하나의 실선이 꿰뚫고 있는 것 처럼. 선형적인 자료구조의 대표적인 예로는 배열이다. 우리는 보통 배열을 그림으로 나타낼 때 왼쪽에서 오른쪽으로, 0, 1, 2, 3… 의 인덱스를 가지고 있다고 가정한다. 하나의 선이 꿰고 있다.
트리를 처음으로 마주할 때에는 마치, 수학에서 수평선에 점으로 정수만 표시하다가, 2차원 평면으로 확장해서 점들의 모임인 그래프를 그리는 것과 같다. 깊이가 생기고 다양한 수의 관계가 생기기 시작하더니 중1의 1차원 방정식부터 고3 심화 미적분까지 다양한 문제들이 기다린다. 트리는 깊이있고, 심화된 문제풀이를 위해서 기본적인 틀이 된다.
그러면 트리는 어떻게 선형적인 자료구조들(배열, 스택, 큐.. 등) 과 다르게 어떻게 깊이를 표현할 수 있을까? 그것은 바로 관계 에 있다.
트리는 기본적으로 부모-자식 관계로 부터 출발한다. 부모와 자식은 각각 ‘노드’ 라고 불리우는데 트리를 구성하는 가장 기본단위가 된다. 노드는 두가지 정보를 담고있는데, 다른 노드와의 차별점을 두는 데이터와, 자식들과의 관계를 담고있는 정보다.
가족 구성원을 떠올려보면 좋을 것 같다. 우리가 가계도를 그릴 때에, 각각 고유한 이름을 가지고 있지만, 선으로 연결 하듯이. 우리는 선을 따라서 올라가면 할아버지의 이름, 증조 할아버지의 이름도 알 수 있고, 증조 할아버지의 형제 자매들의 이름도 알 수 있다. 반대로, 증조 할아버지로 부터 선을 타고 내려오면 자식 들이 누군지 단번에 확인이 가능하다.
컴퓨터 메모리 구조 안에서는 트리가 어떻게 작동할까? 부모는 자식노드들의 ‘주소’를 갖고 있는다. 항상 우리가 부모님과의 관계를 증명하기 위해서 따라다닐 필요가 없듯이, 메모리에서도 같은 노드안에 부모와 자식 노드의 데이터가 같이 저장되는 것이 아니다. 우리가 사는 세계에서 부모과 자식과의 연결을 위해 항상 24시간 붙어 있지 않아도 되는 것 처럼 말이다. 그저 핸드폰 번호만 알고 있으면, 전화를 통해서 연결될 수 있다. 메모리 안에서도 부모는 그저 자식 노드들이 저장되어 있는 메모리 주소(핸드폰 번호)만 알고 있으면 연결이 된 것이고, 언제든지 부모에서 자식으로 접근이 가능하다.
구현
구현의 핵심은, 위에서 설명한 부모노드에 자식과의 관계(주소)를 어떻게 저장할 것인가? 에 대한 질문에서 시작된다.
배열을 이용하면 된다. 배열에 자식노드들의 주소를 담으면 된다. 자식노드를 생성하고 배열에 담으면, 자바스크립트는 알아서 주소를 맵핑 해 준다. 자식을 삭제하기 위해서는 배열에서 해당하는 원소만 제거 해 주면 해당하는 자식 노드의 정보(주소)가 사라진다.
구현은 다음과 같다.
BFS(Breadth Frist Search)
기본개념
너비우선탐색을 해 보자. 우리는 부모-자식 관계를 통해서 트리의 계층이 생긴것을 확인했다. 이 트리를 탐색(순회) 하는 방법 중 하나가 바로 너비우선탐색이다. 너비=층 으로 이해하면 좋을 것 같다. 트리의 가장 최상위 부모부터 자식들의 정보가 궁금하다. 트리 자료구조가 사용되는 일상의 또 다른 예로는 회사의 사내 조직도 인데, 가장 높으신 분(?) 으로 부터 일반 평사원까지의 정보를 알고 싶다면, 층을 따라서 위에서 부터 아래로 내려오면 된다. 사장-부장-대리-사원 이런식으로 층을 따라 사장, 부장, 대리, 이름을 쭉 나열하고, 그 다음 평사원의 이름을 쭉 나열하면 된다. 탐색을 하는데 있어서 우선순위가 너비=층 이 된다는 것이 핵심이다.
구현
층의 구분을 어떻게 할것인가? First in First Out 구조를 가진 큐를 사용하면 어떨까? 계층이 우선 순위니까, 층마다 우선순위를 가지면 된다. 큐의 이름을 unvisitedQueue(방문하지 않은 노드들이 담여있는 큐)라고 하자 이 큐에 노드가 담겨있으면, 아직 방문하지 않은 노드들이 있는 것이다. 우리의 목표는 모든 노드를 방문하는 것! 그렇기 때문에 while 문의 조건문에 큐의 길이를 매번 체크 해 준다.
노드를 빼내면서 그에 해당하는 자식들은 아직 방문하지 않았으니까 큐에 추가 해 준다. unvisitedQueue.push(...current.children)
자동으로 큐에는 자식들의 주소가 쌓일 것이고, 같은 너비=층의 노드들 뒤에 자식들의 주소가 붙으니까, 항상 해당하는 층의 노드를 모두 방문해야 그 아래층인 자식층으로 내려갈 수 있게 된다.
DFS(Depth Frist Search)
기본개념
깊이우선탐색은 위의 너비우선탐색에서 아주 조금만 변형하면 쉽게 구현할 수 있다. 결국 방문해야 할 우선순위의 차이인 것인데, 너비우선탐색은 층 이 우선이 되었지만, 이번엔 깊이 즉, 자식들이 우선순위가 된다. 부모로 부터 자식까지 아래로 쭉 훑고, 그 옆의 부모 노드로 방문이 넘어가게 된다.
아까 회사 조직도에서 너비우선탐색은 한 계급(층)으로 이름을 나열했는데, 깊이우선탐색은 부서 단위라고 보면 좋을 것 같다. 회사의 조직도에서 사장 다음에 영업부서, 개발부서, 디자인부서가 있다고 한다면, 각각의 부서에서는 부장-대리-사원이 있다. 이 회사의 구성원들을 깊이우선탐색으로 이름을 나열하면, 영업부서의 부장-대리-사원, 개발부서의 부장-대리-사원, 디자인부서의 부장-대리-사원 순으로 이름이 나열될 것이다.
구현
그렇다면, 깊이(위의 예에서 부서)의 구분을 어떻게 할 것인가? 라는 질문을 던질 수 있다. 층을 구분 할 때에는 큐의 뒤에다가 계속해서 자식을 쌓으면 자연스레 구분이 되었다. 우선순위가 어디에 있는가 생각하면 조금은 쉽게 문제가 해결된다.
결국, 내 부서 팀원, 내 자식이 중요하다. 그럼? 아까 unvisitedQueue 의 앞에다가 내 자식들의 정보를 먼저 넣어주면 되지 않을까? BFS의 구현과 차별을 두기 위해서 unvisitedQueue => unvisitedList 로 바꾸었다.
그리고 unvisitedQueue.push(...current.children) 이 부분을 unvisitedList.unshift(...current.children) 으로 바꾸었다. unshift 메소드는 자바스크립트 배열 객체의 기본제공 메소드인데, 배열의 맨 앞에 데이터를 넣어준다. 이렇게 함으로써 우선순위가 내 자식들이 먼저가 된 것이다.
실행코드
이 코드를 실행하고 나면 lettersBFS 배열에는 [‘a’, ‘b’, ‘d’, ‘c’] 가 담기고, lettersDFS 배열에는 [‘a’, ‘b’, ‘c’, ‘d’] 가 담긴다.
마치며
글로 표현하려니까 어렵다. 앞으로는 자료구조와 알고리즘에 대한 글을 쓸 때에는 내가 스스로 납득하고 이해할 수 있는 쉬운 예들을 많이 떠올리기 위해 노력해야 겠다.
