깊이 우선

[알고리즘] DFS (Depth-First Search) / C++ 구현

1. DFS란? DFS는 Depth-First Search 의 줄임말로 “깊이 우선 탐색"이라고 부른다. DFS의 가장 큰 특징은 해당 노드가 더 이상 edge를 가지지 않을 때까지 따라 가다가, leaf Node에서 Back Track 하는 방식을 사용하여 탐색한다는 것이다. 즉, 중요한 것은 더 이상 edge가 없는 Node를 만났을 때, Back Track을 수행한다는 것이다. DFS 순회는 다음과 같다. end end end end end 리스트로 구현한 DFS에서 N이 모든 Node의 개수이고, M은 Node를 모두 탐색하기 위한 Edge의 개수 일 때, 단지 Node들과 필요한 Edge를 한번씩 방문하면 되기 때문에 시간 복잡도는 BFS와 마찬가지로 다음과 같다. O(|V| + |E|) 2. ..

[알고리즘] BFS ( Breadth-First Search) / C++ 구현

1. BFS란? BFS는 Breadth-First Search 의 줄임말로 “너비 우선 탐색"이라고 부른다. BFS의 가장 큰 특징은 layer의 순서대로 탐색한다는 것이다. 즉, 탐색을 시작하는 지점인 root node에서 가까운 순서대로 탐색을 수행한다. 예시로 든 다음 트리에서 1층 레이어에 10, 2층 레이어에 4와 9, 3층 레이어에 3과 1과 2와 7, 마지막 4층 레이어에 5와 6으로 이루어져 있는 것을 볼 수 있다. BFS는 이 레이어의 층 수 대로 한 층씩 내려오면서 탐색하는 방법을 뜻한다. 결국 위 트리의 BFS 순회는 다음과 같다. layer-1 layer-2 layer-3 layer-4 Queue를 이용한 리스트로 구현한 BFS에서 N이 모든 Node의 개수이고, M은 Node를 모..