DFS(깊이 우선 탐색)
개념 요약
- 그래프 알고리즘으로 루트 노드 혹은 임의의 노드에서 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방법이다.
- 스택, 재귀 함수를 통해 구현할 수 있다.
- 모든 경로를 방문해야 할 경우 사용하기에 적합하다.
- 한 방향으로 갈 수 있을 때까지 계속 전진하며 전진할 수 없을 때, 가장 가까운 갈림길로 돌아와서 다시 한 방향으로 전진한다.
- 방문했는지의 여부를 판단해야 한다.
코드
// 재귀
void dfs(Node &root)
{
// 해당 노드가 끝에 도달
if (root == nullptr)
return ;
else
{
// 해당 노드의 방문 여부 재설정
root.visited = true;
// 해당 노드와 연결된 노드로 재귀
for (Node &connected_node : root.connect_node)
{
// 해당 노드의 방문 여부 확인
if (connected_node.visited == false)
dfs(connected_node);
}
}
}
--------------------------------------------------------------
// 스택
void dfs(Node &root)
{
// 스택 생성
stack<Node> store;
// 스택 초기값 설정
store.push(root);
// 스택이 빌때까지 루프
while (store.empty() == false)
{
// 스택의 가장 위의 노드를 현재 노드로 설정
Node &curr_node(store.top());
// 현재 노드의 방문 여부 재설정
curr_node.visited = true;
// 스택의 가장 위 pop
store.pop();
// 현재 노드와 연결된 노드 스택에 push
for (Node &connected_node : curr_node.connect_node)
{
// 해당 노드의 방문 여부 확인
if (connected_node.visited == false)
store.push(connected_node);
}
}
}
장단점
- 목표 노드가 깊은 곳에 있는 경우 해를 빨리 구할 수 있지만, 그렇지 않다면 더욱 느리게 탐색된다.
BFS(넓이 우선 탐색)
개념 요약
- 루트 노드 또는 임의의 노드에서 인접한 노드부터 먼저 탐색하는 방법이다.
- 큐를 통해 구현한다.
- 최소 비용에 적합하다.
코드
void bfs(Node &root)
{
// 큐 생성
queue<Node> store;
// 초깃값 push
store.push(root);
// 큐가 빌때까지 루프
while (store.empty() == false)
{
// 큐에 저장된 가장 앞 노드를 현재 노드로 지정
Node &curr_node = store.front();
// 현재 노드의 방문여부 재설정
curr_node.visited = true;
// 큐의 저장된 가장 앞 노드 pop
store.pop();
// 현재 노드와 인접한 노드 큐에 push
for (Node &connected_node : curr_node.connect_node)
{
// 해당 노드의 방문여부 확인 후 큐에 push
if (connected_node.visited == false)
store.push(connected_node);
}
}
}
장단점
- 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
- 노드의 수가 늘어나면 탐색해야 하는 노드도 많아지기 때문에 비현실적이다.