JavaScript로 이진트리, 그래프, BFS 구현하기
문제분석
이진트리에서 타겟노드부터 같은 거리에 있는 모든 노드의 값을 담아서 리턴하는 함수를 구현하기
함수의 인자로 3개의 인자가 들어온다.
- 이진트리의 뿌리: root
- 이진트리 안에 타겟노드: target
- 거리: K
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
돌파구
이 문제를 풀기 위해서는 다양한 방법이 존재하는데, 내가 이 문제를 접했을 때, 가장 먼저 떠오른 방법으로 구현하길 원했다.
- 먼저, 이진트리를 Graph로 구성하기
- 1에서 만든 Graph 에 대해 BFS 알고리즘 적용하기: 해당 거리까지 탐색해서 같은 거리의 있는 노드들의 값을 배열에 담아서 리턴하기
하지만, Graph를 어떤 방식으로 구현하고, Graph에 BFS 알고리즘을 활용해본적은 없기 때문에 애를 먹었다. 하지만, 이 문제를 통해서, 트리를 그래프로 구현하고, 그래프에 대해서 BFS 알고리즘을 적용 해 보았기 때문에 수확이 많은 문제였다.
구현
코드의 구현도 위와 같이 두 부분으로 나뉘는데
- dfs 알고리즘으로 이진트리를 Graph(JavaScript Object) 에 담기
- dfs 를 거쳐서 만든 Graph에 대해서 BFS 알고리즘 적용하기
DFS
- 트리를 그래프로 만들기 위해서는 먼저 dfs 함수 내에서 계속해서 값이 저장될 graph Object 가 있어야 한다. (Key, Value)로 값을 저장할 것이기 때문에.
- Graph Object의 모습은 다음과 같다.
Key: node.val, Value: neighbor array [parent.value, left.value, right.value]
이진트리를 그래프로 바꾸는 dfs recursive 함수 내 로직
- node === null 일 때, 엔딩조건
- 해당하는 노드에 대해서 neighbor 배열을 생성하고, 넘겨받은 parent 와 left, right 를 모두 null로 초기화한다.
- 왼쪽, 오른쪽 노드가 존재하면 값을 갱신한다. 그리고, 똑같은 일을 반복하도록 dfs 재귀 호출
- 그래프에 Key: node.val, Value: neighbor 배열을 저장한다.
BFS
그래프의 BFS 알고리즘의 핵심은, 큐와 셋을 사용한다는 것!
- unvisitedQueue: 아직 방문하지 않은 노드들이 담겨있다.
- visitedSet: 이미 방문한 노드들을 담는다. (탐색된 노드는 또 탐색하지 않게 만들기 위해서 중복을 제거하는 자료구조인 Set을 사용한다.)
- while 문이 BFS의 로직인데, 먼저 Queue 에서 꺼내서, 이미 방문한 노드라면 다시금 방문하지 않도록
continue문을 사용한다. - 한가지 더 주목할 점은, 타겟노드로 부터의 거리를 알기 위해서 큐에다가 value 와 distance 를 함께 담는 것!
- 탐색을 지속 해 나간다는 뜻은, queue에 탐색 할 아이들을 넣어주는 것인데, 이 때, 타겟노드로 부터의 거리를 함께 저장 해 주어야 한다. 이때, 거리를 1 증가 시켜줘야 한다. 왜냐하면, 탐색을 지속한다는 것은 레벨이 한 층 증가된다는 것이기 때문에.
