반응형
BFS (너비 우선 탐색)

BFS의 장점
- 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
- 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
- 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
- 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.
BFS의 단점
- 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
- 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.
BFS 구현
Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다.
- Queue에서 하나의 노드를 꺼냅니다.
- 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다.
/* BFS 코드 구현 */
public void bfs(Node root) {
Queue<Node> qu = new LinkedList<Node>();
Node temp = root;
qu.add(temp);
while(!qu.isEmpty()){
/* 큐에서 뽑아서 바로 출력 시킨다. */
temp = qu.poll();
System.out.println(temp.value + " -> ");
if(temp.left != null) // temp.left가 있으면 큐에 추가.
qu.add(temp.left);
if(temp.right != null)
qu.add(temp.right); // temp.right가 있으면 큐에 추가.
}
}
더보기
boolean 배열 visit로 해당 노드의 왼쪽, 오른쪽 노드를 방문했는지 체크 하면서 탐색하는 방법도 있다.
/* 내가 짠 코드 */
public void bfs(Node node) {
Queue<Node> qu = new LinkedList<Node>();
boolean[] visit = {false,false};
Node temp = this.root;
qu.add(temp);
while(!qu.isEmpty()){
temp = qu.peek(); // qu에서 하나를 뽑는다.
if(!visit[0]){
if(temp.left != null) {
qu.add(temp.left);
visit[0] = true;
}else{
System.out.print(qu.poll().value + " -> ");
}
}else if(!visit[1]){
if(temp.right != null) {
qu.add(temp.right);
visit[1] = true;
}else{
System.out.print(qu.poll().value + " -> ");
}
}else if(visit[0] && visit[1]){
visit[0] = false;
visit[1] = false;
System.out.print(qu.poll().value + " -> ");
temp = qu.peek();
}
}
}
DFS (깊이 우선 탐색)

DFS의 장점
- 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있는 경우 빠르게 구할 수 있다.
- 구현이 너비 우선 탐색(BFS) 보다 간단하다.
DFS의 단점
- 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느리다.
- 결과 값이 없는 경로에 깊이 빠질 가능성이 있다.
DFS 코드 구현
- 중위순회(In-order) 방식과 동일
/* DFS 코드 구현 */
public void dfs(Node node) {
if(node != null) {
dfs(node.left);
System.out.println(node.value + " -> ");
dfs(node.right);
}
}
📄 REFERENCES
coding-factory.tistory.com/611?category=794828
coding-factory.tistory.com/612
반응형
반응형
BFS (너비 우선 탐색)

BFS의 장점
- 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
- 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
- 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
- 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.
BFS의 단점
- 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
- 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.
BFS 구현
Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다.
- Queue에서 하나의 노드를 꺼냅니다.
- 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다.
/* BFS 코드 구현 */
public void bfs(Node root) {
Queue<Node> qu = new LinkedList<Node>();
Node temp = root;
qu.add(temp);
while(!qu.isEmpty()){
/* 큐에서 뽑아서 바로 출력 시킨다. */
temp = qu.poll();
System.out.println(temp.value + " -> ");
if(temp.left != null) // temp.left가 있으면 큐에 추가.
qu.add(temp.left);
if(temp.right != null)
qu.add(temp.right); // temp.right가 있으면 큐에 추가.
}
}
더보기
boolean 배열 visit로 해당 노드의 왼쪽, 오른쪽 노드를 방문했는지 체크 하면서 탐색하는 방법도 있다.
/* 내가 짠 코드 */
public void bfs(Node node) {
Queue<Node> qu = new LinkedList<Node>();
boolean[] visit = {false,false};
Node temp = this.root;
qu.add(temp);
while(!qu.isEmpty()){
temp = qu.peek(); // qu에서 하나를 뽑는다.
if(!visit[0]){
if(temp.left != null) {
qu.add(temp.left);
visit[0] = true;
}else{
System.out.print(qu.poll().value + " -> ");
}
}else if(!visit[1]){
if(temp.right != null) {
qu.add(temp.right);
visit[1] = true;
}else{
System.out.print(qu.poll().value + " -> ");
}
}else if(visit[0] && visit[1]){
visit[0] = false;
visit[1] = false;
System.out.print(qu.poll().value + " -> ");
temp = qu.peek();
}
}
}
DFS (깊이 우선 탐색)

DFS의 장점
- 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있는 경우 빠르게 구할 수 있다.
- 구현이 너비 우선 탐색(BFS) 보다 간단하다.
DFS의 단점
- 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느리다.
- 결과 값이 없는 경로에 깊이 빠질 가능성이 있다.
DFS 코드 구현
- 중위순회(In-order) 방식과 동일
/* DFS 코드 구현 */
public void dfs(Node node) {
if(node != null) {
dfs(node.left);
System.out.println(node.value + " -> ");
dfs(node.right);
}
}
📄 REFERENCES
coding-factory.tistory.com/611?category=794828
coding-factory.tistory.com/612
반응형