[알고리즘] BFS 정리

리트코드 - leetcode.com/problems/serialize-and-deserialize-binary-tree/

 

구글 인터뷰 문제 TOP10 중 2 위인 BFS 알고리즘

BFS 는 트리 구조의 Data를 너비 먼저 탐색하는 (Breath First Search) 알고리즘이다.

 

 

출저 - https://www.guru99.com/breadth-first-search-bfs-graph-example.html

 

 

꼭 binary tree 가 아니여도 된다.

 

 

출저 - https://open4tech.com/bfs-vs-dfs/

 

 

BFS	DFS
▪ 깊이가 얕고 노드가 적을 때 유리 ▪ DFS 보다 메모리를 더 많이 쓸 수 있다.    탐색할 모든 노드를 큐에 저장 ▪ 큐 (Queue) ▪ 답이 되는 경로가 최단경로 보장	▪ 깊이가 깊고 노드가 많을 때 유리 ▪ BFS 보다 메모리를 더 적게 쓴다.   백트래킹을 해야하는 노드만 저장 ▪ 스택 (Stack), 재귀 (Recursive) ▪ 끝까지 찾아봐야 최단경로를 알 수 있다.

 

 

 

 

leetcode.com/problems/serialize-and-deserialize-binary-tree/

Serialize and Deserialize Binary Tree - LeetCode

 

 

위 문제는 binary tree 가 주어지고 그 트리를 serisiserialize (tree를 single string 으로 encode) 한 다음,

만들어진 string value를 다시 binary tree로 deserialize 하여 (encode 된 data를 다시 tree로 decode) 리턴 해주는 문제이다.

 

 

보통 트리를 그림이아닌 [ ] 나 string 으로 표현할 때 노드가 나열된 순서가 BFS의 탐색순서와 같다는 것을 알 수 있다.하지만 이문제는 DFS 로도 풀 수 있다.

 

BFS는 Queue를 이용한다.

큐는 FIFO (First-In-First-Out) 의 컨셉을 가진 Data structure이다. 큐는 입력된 순서대로 출력된다. 마지막에 입력된 것이 처음으로 나오는 LIFO (Last-In-First-Out) 인 Stack 과 다른 점이다.

 

아래 그림처럼 큐에 data가 1,2,3,4,5,6,7 순서대로 입력(Enqueue) 되었을 때, Dequeue 하면 제일 처음 입력된 data 1이 out 되는 것을 알 수 있다.

큐를 트리 탐색에 이용하는 방법을 아래 그림 트리로 설명하자면,

먼저 최상위 level 에 있는 루트 노드 A 를 큐에 넣어주고 자식 노드들을 넣어줄 Loop 를 시작한다.

 

Loop는 큐에 저장된 노드가 다 출력되 Empty가 될 때까지 진행한다.큐에 입력된 노드를 FIFO 순으로 출력하여 출력된 노드의 자식 노드들을 큐안에 넣어준다. 그리고 큐에 입력된 자식노드들을 다시 출력하여 또 그 노드들의 자식 노드들을 큐안에 넣어준다.

 

Loop가 시작되면 Loop 전에 넣었던 A를 빼서 A의 자식 노드인 B,C,D를 넣어준다.

입력된 순서대로 B를 빼서 B의 자식 노드인 E,F를 넣어준다.

그다음 입력된 C를 빼서 C의 자식 노드인 G,H를 넣어준다.

 

출저 - https://www.guru99.com/breadth-first-search-bfs-graph-example.html

 

트리를 String 으로 바꾸는 serialize method

 

위의 설명처럼 while loop 안에서 queue 에 입력된 node 들을 poll( )로 빼내어 그 자식들을 다시 offer( ) method로 입력해준다. Queue 안에 자식 node 들이 계속 입력되기 때문에 모든 트리 노드들을 탐색할 때까지 loop는 지속된다.

 

String 을 트리로 바꾸는 deserialize method

binary tree 이기 때문에 string의 index를 이용해 자식트리를 구분할 수 있다.

 

 

Note
serialize method 에서 StringBuilder 대신 String을 사용하면 runtime 이 10배가 넘게 든다
이유는 String 과 StringBuilder/StringBuffer의 각각 immutable/mutable 특징을 갖는 저장방식이 다르기 떄문이다.

String은 기존의 값인 Hello 에서 HI를 더할 때 기존의 값을 수정하는 것이 아니라 HelloHi 라는 새로운 data를 만들고 기존의 Hello 값은 Garbage 가 된다. 이 점을 보완하기 위해 StringBuffer 와 StringBuilder 는 기존의 data인 Hello를 수정할 수 있게 만들어졌다. 

StringBuffer와 StringBuilder의 차이점은 StringBuffer는 멀티쓰레드에서 동기화를 지원하고 StringBuilder는 지원하지않는다. 
단일 Thread 에서는 StringBuilder 가 제일 빠르다.