brute Force

Bredth-First-Search (너비 우선 탐색)란? BFS의 원리는 간단하게 말하면 퍼지는 물결파 이다. 잔잔한 호수에 돌을 던져 생기는 물결파를 떠올려 보자. 동그란 원형의 파원을 일으키며 퍼져나간다. 이렇게 동일한 거리의 지점들은 동시에 탐색을 하는 방법이다. 핵심은 1번의 탐색 루틴에서 하나의 level에 있는 모든 정점을 탐색한다는 것이다. 저번 DFS처럼 BFS방식을 그래프를 통해 설명해보겠다. 앞서 DFS에서 사용한 그래프와 동일한 형태의 그래프다. DFS와 마찬가지로 1번 정점부터 탐색을 시작해보자. 1번 정점을 탐색 완료했다면 현재 정점의 인접하는 정점들을 확인한다. BFS는 다음에 탐색할 위치를 인접한 모든 정점으로 선택한다. 따라서 다음 탐색은 2, 3번 정점으로 이동한다. 원리..

그래프 탐색 (Graph Search) 앞서서 그래프를 배웠다. 트리에 트리를 탐색하는 트리 순회가 있었다면, 그래프는 그래프 탐색이 존재한다. 그래프 탐색 방법에는 DFS와 BFS가 존재한다. 이번 글에서는 DFS에 대해서 이야기할 예정이다. 그래프 탐색을 배우는 이유는 그래프의 이동 경로나 생김새를 파악하기 위해서 사용한다. 탐색을 통해서 그래프에 사이클이 몇개고, 전체적인 묶음이 몇개인지 알 수 있기때문이다. DFS VS BFS DFS는 깊이 우선 탐색(Depth-First-Search)의 약자이고 BFS는 너비 우선 탐색(Bredth- First-Search)의 약자이다. 이름에 탐색 방식이 들어가 있다. DFS는 깊게 들어가는 것을 우선으로 하는 탐색방식이고 BFS는 넓은 분포, 즉 한 leve..