BFS
BFS은 탐색 방식의 한 종류이다.
넓이 우선 탐색이라는 것인데, DFS와 비슷하면서 다른 탐색방식이다.
해당 부분에 대해서는 아래 링크를 참조하면 참 좋다.
https://half-forty.tistory.com/77
JAVA_코딩테스트 준비_탐색 알고리즘_(BFS/DFS)
BFS / DFS 그래프에서 탐색은 배열에서 나열된 요소들을 보는것과 달리 마치 무작위로 흩뿌려져 있는것들을 일일히 들여다 보는것과 비슷한 형태를 띈다. 그래서 특정한 값을 찾고 싶거나, 최단거
half-forty.tistory.com
BFS는 코딩 테스트에서 사용하는 유형에 따라 DFS 대신에 선택해야 한다.
- 경로 탐색 시, 원하는 경로 상의 "레벨" 이 중요한경우 (트리 레벨)
- 비교적 작은 규모의 탐색인 경우
- 재귀함수를 사용하지 않고 탐색해야 하는 경우
대략 이정도 이유를 들 수 있는데, 물론 다른 이유도 많을것이다.
BFS는 DFS와 달리 재귀함수를 사용하지 않고 구현하는게 일반적이다.
물론 DFS도 스텍을 사용해서 재귀 없이 풀 수 있다.
그런데 BFS는 큐(Queue)를 사용한다.
자료구조 큐(Queue)에 관한 포스팅은 아래 링크를 참조하자.
https://half-forty.tistory.com/73
JAVA_자료구조_큐(Queue)
자료구조 자료구조란 쉽게 말해서 일종의 주머니다. 우리가 intm String등등의 자료를 사용 했는데 이들 모두 자료구조의 일종이다. 한개의 값을 가질때는 단순구조인 int, char 형 변수 등이 사용되
half-forty.tistory.com
나처럼 재귀를 사용하는것에 대해 헷갈려 하는 사람은반갑게 생각 할 수 있다.
대신 큐에 대해 잘 이해 해야 하므로 꼭 알아두자
해당 문제를 플 때 추가적으로 트리 구조에 대해 알아야 한다.
https://half-forty.tistory.com/74
JAVA_자료구조_트리(Tree)
Tree Tree(트리)는 말 그대로 나무와 비슷한 형태를 가진 자료구조이다. 그런데 우리가 아는 나무가 아니고, 거꾸로 서있는 나무 모양이다. (약간, 토너먼트 대진표랑 비슷한 형태라고 생각하면 된
half-forty.tistory.com
https://half-forty.tistory.com/76
JAVA_자료구조_(Binary Search Tree, 트리 순회)
1. Binary Search Tree 트리구조는 편리한 구조를 전시하는것 이외에 효율적인 탐색을 위해 사용되기도 한다. 대표적으로 이진 트리가 있다. 이진 트리는 자식 노드가 최대 2개씩만 존재하는 노드로
half-forty.tistory.com
이진 트리 순회 (BFS)
위와 같은 7개의 요소를 가진 이진 트리가 있다.
이를 순화하는 BFS를 만들어보자
BFS는 DFS 처럼 한 경로 쭈우욱 가다가 막히면 되돌아 오는게아니고, 우리가 뷔페에서 밥먹을때마냥 쬐끔찍 찍먹하고 다니는거다.
그래서 BFS가 돌아다닐때는 레벨단위로 돌아다닌다.
위의 그림을 보면 0, 1, 2 로 레벨을 나누어 놧는데 이 레벨별로 탐색을 한다고 치면
0 레벨 : 1
1 레벨 : 2, 3
2 레벨 : 4, 5, 6, 7
으로 나타낼 수 있다.
이때 코스상에서 구현 할 때 고려해야 하는것이 "부모노드와 자식노드의 연결관계"와 "BFS가 끝나는 지점"을 고려해야 한다.
이제 코드로 구현해보자
코드 예시
import java.util.LinkedList;
import java.util.Queue;
class Node{ // 노드 설정해주는 클래스
int data;
Node lt , rt ; // 노드의 자식노드 lt:왼쪽 자식노드 , rt : 오른쪽 자식노드
public Node (int val){
data = val;
lt=rt=null; // 왼쪽, 오른쪽 자식노드를 null 초기값으로 넣음
// 이렇게 만들어 놓으면, 말단 노드 부분에서 null값이 들어간 자식노드가 생기는데, 이걸 이용해서 bfs 멈춤
}
}
public class BIBFS {
Node root;
public void BFS(Node root){
Queue<Node> Q = new LinkedList<>();
Q.offer(root); // 큐에 루트값 먼저 하나 넣고 ㄱㄱ 함
int L = 0 ; // 처음 시작하는 레벨
while(!Q.isEmpty()){
int len = Q.size();
System.out.print(L + " : ");
for(int i = 0 ; i < len ; i ++){
Node cur = Q.poll(); // 큐 안에 들은거 꺼내기 하나씩 꺼냄
System.out.print(cur.data + " ");
if(cur.lt != null){ // 왼쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.lt);
}
if(cur.rt != null){ // 오른쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.rt);
}
}
L++; // 탐색 레벨 높이기
System.out.println(); // 줄바꿈
}
}
public static void main(String[] args) {
BIBFS tree =new BIBFS(); //1(루트)~7 를 가지는 이진 트리 생성 (일일히 숫자 넣은거임)
tree.root = new Node(1);
tree.root.lt = new Node(2);
tree.root.rt = new Node(3);
tree.root.lt.lt = new Node(4);
tree.root.lt.rt = new Node(5);
tree.root.rt.lt = new Node(6);
tree.root.rt.rt = new Node(7);
tree.BFS(tree.root);
}
}
위의 코드를 보에서 Node 클래스는 그냥 트리 구조를 만들기 위해 왼쪽, 오른쪽 자식 노드를 만들어주는클래스고
아래쪽의 tree.root 줄줄줄 써놓은건 그냥 트리에 직접 숫자 넣어준것이다.
핵심은 BIBFS 메서드에 있다.
코드를 찬찬히 읽어보면 이해하기 쉽다
먼저 간단하게 설명하면
- 큐 자료형에 먼저 루트 노드를 넣고
- 해당 노드를 출력하면서 큐에서 빼는데
- 루트노드에 연결된 자식노드들을 큐에 넣어준다.
- 이후 큐에 들어간 순으로 빼주면서 출력하고, 빼는 숫자와 연결된 노드들을 또 큐에 넣어준다.
- 더이상 넣을거 없을때 까지 반복하게 됨 = 큐가 다 비엇음 (Q.isEmpty()가 true일때 끝)
?
글로 쓰니까 모르겟다고?
그림으로 알려준다
먼저, 루트 노드(1)을 큐에 넣는다
그리고, while문 안의 코드를 실행하게 되는데, 이때 "1"만 큐에 들어갔으니 for문은 한번만 돌게 된다.
그러면
Node cur = Q.poll(); // 큐 안에 들은거 꺼내기 하나씩 꺼냄
System.out.print(cur.data + " ");이 코드로 인해서 큐 안에 들어있는 1을 꺼내서 출력하게되고, 이때의 큐 상태는 이렇게된다.
벌써 레벨 0 의 요소 출력한것이다. 이제 레벨 1을 보자
if(cur.lt != null){ // 왼쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.lt);
}
if(cur.rt != null){ // 오른쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.rt);
}1과 연결되어 있는 왼쪽, 오른쪽 자식노드를 큐에 넣는다.
그러면 이때의 큐는 이렇게 된다.
이 상태에서 다시 위로 올라가서 L = 1인 상태로 while문 안의 코드를 시작하게 된다.
Node cur = Q.poll(); // 큐 안에 들은거 꺼내기 하나씩 꺼냄
System.out.print(cur.data + " ");위의 코드로 일단 앞에 하나 꺼내서 출력한 큐의 상태는
이렇게 되는데, 이 상태에서
if(cur.lt != null){ // 왼쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.lt);
}
if(cur.rt != null){ // 오른쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.rt);
}을 실행하면 2의 왼쪽, 오른쪽 자식노드가 큐에 들어가고
이 상태에서 또 for문 초장의 코드
Node cur = Q.poll(); // 큐 안에 들은거 꺼내기 하나씩 꺼냄
System.out.print(cur.data + " ");를 실행하면 3이 출력되면서 -> 1레벨에 있는 2, 3 둘다 출력 완료
큐 메모리가 4 5 만 남을 때 또 아래의 코드를 실행 시키면 3의 자식 노드를 넣는다.
if(cur.lt != null){ // 왼쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.lt);
}
if(cur.rt != null){ // 오른쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.rt);
}이 코드를 실행시키면 큐의 상태가
이렇게 되고 for문이 끝난다.
그러면 아래의 L++ 덕분에 또 레벨이 올라가고, 레벨 2 탐색을 시작한다.
하지만 4, 5, 6, 7 노드에는 자식노드가 없다
for문은 4, 5, 6, 7 이 들어있는 큐의 크기 : 4번이 돌아가게 되어 있고, 자식노드가 잇으면 큐에 넣으라 햇는데 없는 상태이다.
for(int i = 0 ; i < len ; i ++){
Node cur = Q.poll(); // 큐 안에 들은거 꺼내기 하나씩 꺼냄
System.out.print(cur.data + " ");
-------------- 동작 안함 --------------------------
if(cur.lt != null){ // 왼쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.lt);
}
if(cur.rt != null){ // 오른쪽 말단 노드가 null이 아니면 큐에 값을 넣음
Q.offer(cur.rt);
}
-------------- 동작 안함 --------------------------
}그러면 단순히 큐에서 하나씩 꺼내서 출력하면서 BFS가 끝나게 된다.
이것으로 이진트리 BFS는 뿅!
PS : DFS, BFS를 공부하는데 자꾸 DFs 먼저 공부해서 재귀생각하면서 혼자서 헷갈리는 경우가많앗다...
다행히 블로깅 하면서 이해하고 해결한거 같은데 이 글 쓰는데 왜이렇게 오래 걸리냐...(2~3시간 걸린듯)
막상 BFS 해보니까 엄청 단순한데 이게 과연 이렇게 얌전한 문제로 나와줄까가 의문이긴 하다.
경우에 따라서는 DFS보다 BFS로 코테 통과하는게 코드 푸는 시간 상으로 유리할수도... 성능은 모르겟지만
'백엔드 > JAVA_코딩테스트' 카테고리의 다른 글
| JAVA_코딩테스트 준비_부분집합_(DFS) (0) | 2023.02.21 |
|---|---|
| JAVA_코딩테스트 준비_이진트리순회 (DFS) (0) | 2023.02.20 |
| JAVA_코딩테스트 준비_순열/조합 (2) | 2022.11.28 |
| JAVA_코딩테스트 준비_ 알고리즘, 의사코드 (1) | 2022.11.28 |
| JAVA_코딩테스트 준비_이진 탐색 알고리즘 (Binary Search Algorithm) (0) | 2022.11.28 |