STUDY/알고리즘

BFS 개념 Breadth First Search 노드를 방문하고 너비 우선으로 인접한 노드를 방문한다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장 후 가장 처음에 넣은 노드를 꺼내서 탐색 가장 처음에 넣은 노드 -> 큐(Queue) 이용하는 것이 적합 1. 루트 노드를 큐에 저장 2. 현재 큐의 노드를 빼서 visited 에 추가 (방문처리) 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가 4. 2부터 반복. 5. 큐가 비면 탐색 종료 BFS 구현 조금 더 확실히 하기 위해 각 노드에 붙은 숫자를 섞어보았다. 위와 같이 DFS인 척 하는 그래프가 있다고 해보자. 우리는 이 그래프를 BFS로 탐색하려고 한다. 그러면 탐색 순서는 이러한 형태가 되어야 할 것이다. 이를 딕셔..

DFS & BFS? 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. 왜 DFS & BFS 를 배울까요? 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는 경우도 있습니다. DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있습니다. DFS 는 끝까지 파고드는 것이고, BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점입니다. DFS 끝까지 파고드는..