TIL 2022-06-17
알고리즘
1. BFS는 재귀와 관계가 없다.
DFS는 재귀함수를 사용하여 접근하는게 일반적이다. BFS문제를 처음 접하고 문제에 관한 State Space Tree를 설계했지만 재귀함수로 구성하는데 무언가 문제가 있었다.
재귀함수로 구성하기 적절하지 않음
1.
DFS의 경우 보통 재귀호출시마다 파라미터의 값(depth, etc.)을 갱신하여 base case에 도달하면 종료하는 구조이다. 하지만, BFS의 경우 depth를 기준으로 종료하는데 무리가 있었다.(애초에 depth로 접근하는 방법도 아닐뿐더러..)
2.
BFS를 위해 큐를 사용했기 때문에 탐색 종료지점은 큐가 비어있는 경우이다. 이를 위해 while문을 사용했는데 while문에서 탈출한다는 것은 모든 방문이 끝났다는 것이고 그럼 재귀호출할 이유가 없게된다.
애초에..
DFS: 스택에 넣으면서 탐색
BFS: 큐에 넣으면서 탐색
이게 무슨 말일까? 다음과 같은 그래프를 DFS, BFS로 탐색한다고 해보자.
BFS에 대한 State Space Tree는 다음과 같다.
너비우선탐색이기 때문에 3 -> 1 -> 2 가 아니라, 3 -> 1 -> 4가 돼야한다.
여기서 큐를 이용하면 어떻게 될까? (큐에 넣는 행위를 방문이라고 정의하자)
1. 시작노드 3 방문
2. 1번노드, 4번노드 방문
3번노드에서 갈 수 있는 자식노드들 큐에 삽입. 즉, 방문한 노드는 삭제하고 유효한 자식노드들은 큐에 삽입하는 구조
1번노드 4번노드 큐에 삽입. 즉, 3번노드에 이어서 1번노드 4번노드 차례로 방문(FIFO) 노드3은 방문이 끝났으니 큐에서 제거.
3. 2번노드 방문
1번노드에서 갈 수 있는 자식노드들 큐에 삽입. 노드1은 방문이 끝났으니 큐에서 제거
4. 5번노드 방문
4번노드에서 갈 수 있는 자식노드들 큐에 삽입.
=> 탐색종료 (큐 Empty)
정리하자면, 큐에 노드를 넣고, 빼면서 다음 방문할 노드를 큐에 넣는 행위 자체가 결국 BFS가 된다.
쉽게말해 큐를 이용한 탐색이 BFS이다.