토피넛라떼조아

지난 포스팅을 통해 DFS를 알아보았으니 형제 탐색법인 BFS를 알아보겠다.BFS 또한 DFS처럼 트리나 그래프를 순회하는 기본 방법 중 하나이다. BFS (Breadth First Search)? BFS는 너비 우선 탐색이다. 시작 노드부터 가까운 노드들을 모두 살펴본 뒤 그 다음 노드들을 탐색한다. 단순하게 생각해서 파원에서 파장이 퍼져나가는 모양을 생각하면 얼추 비슷하다. 특징과 장단점- 연결된 모든 노드를 탐색할 수 있다.- 방문 노드를 기억하고 재방문하지 않는다.- DFS가 스택을 활용하는 것과 다르게 보통 큐를 활용한다.- 최단경로 탐색에 적절하다. 해를 찾고나면 다음 해는 찾을 필요가 없기 때문이다.- 논리 구조가 간단하다.- 해가 깊은 곳에 있으면 탐색에 오랜 시간이 걸릴 수 있다.  BF..

알고리즘 풀이를 놓은 지 시간이 좀 흐르니까 자신만만하던 문제들도 쉽게 풀지 못하는 지경에 이르렀다. 아무래도 정리를 하면서 이해를 하는 시간을 한 번 더 가져야 할 것 같아서 문제 풀이에 기본이 되는 알고리즘들을 다시 코드를 작성하면서 복기해보려고 한다.  자 가장 쉬운 그래프 탐색법인 DFS부터 알아보자수많은 트리, 그래프를 순회하는 방법 중 기본이 되는 알고리즘이다. DFS (Depth First Search)? 이름부터 깊이를 우선하여 서치한다는 의미를 담고 있다. 시작부터 끝까지 '깊이'를 우선하여 탐색한다. 처음에는 깊이를 우선한다는 게 이해가 잘 되지 않을 수 있다. 쉽게 이해하기 위해 미로를 탐험한다고 가정해보자. 무수히 많은 갈림길이 존재할 것이다. 이런 미로를 모두 정복하기 위해 한 방..