DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)

DFS와 BFS는 모두 *그래프를 탐색할 때 사용한다.

*그래프:정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조

하나의 정점에서 시작하여 차례대로 모든 노드들을 순회(방문)하면서 탐색하는 탐색 알고리즘이다.

 

[출처] http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

DFS(깊이 우선 탐색)

; 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 모두 순환하여 탐색하는 방법.

  모든 노드를 방문하고자 하는 경우나 이전 경로의 정보가 필요한 경우에 사용한다.

  최대한 깊이 내려간 뒤에 더 이상 깊이 갈 곳이 없으면 옆으로 이동한다.

  스택(stack) 또는 재귀함수로 구현한다.

 

DFS 구현(재귀)

1. 노드를 방문 리스트에 기록

2. 현재 노드에 인접한 노드를 기준으로 반복

3. 노드의 인접 리스트가 비었을 경우 종료

4. 방문하지 않은 노드일때  재귀호출

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int number = 7;	      // 노드 개수
bool visited[8];      // 방문 리스트
vector<int> graph[8]; // 연결된 숫자를 넣기 위해 배열을 8개 만듬

// 재귀
void dfs(int x)
{
    // 방문했다면 리턴
    if(visited[x])
        return;

    // 방문 체크
    visited[x] = true;
    cout << "visited= " << x << endl;
    
    for(int i = 0; i < map[x].size(); i++)
    {
    	int y = map[x][i];
        cout << x << "->" << y << " / " << "[" << x << "," << i << "]" << endl;
        dfs(y);
    }
}

int main()
{
    // 1 <-> 2
    graph[1].emplace_back(2);    // graph[1] = {2};
    graph[2].emplace_back(1);    // graph[2] = {1};
    // 1 <-> 3
    graph[1].emplace_back(3);    // graph[1] = {2,3};
    graph[3].emplace_back(1);    // graph[3] = {1};
    // 2 <-> 3
    graph[2].emplace_back(3);    // graph[2] = {1,3};
    graph[3].emplace_back(2);    // graph[3] = {1,2};
    // 2 <-> 4
    graph[2].emplace_back(4);    // graph[2] = {1,3,4};
    graph[4].emplace_back(2);    // graph[4] = {2};
    // 2 <-> 5
    graph[2].emplace_back(5);    // graph[2] = {1,3,4,5};
    graph[5].emplace_back(2);    // graph[5] = {2};
    // 3 <-> 6
    graph[3].emplace_back(6);    // graph[3] = {1,2,6};
    graph[6].emplace_back(3);    // graph[6] = {3};
    // 3 <-> 7
    graph[3].emplace_back(7);    // graph[3] = {1,2,6,7};
    graph[7].emplace_back(3);    // graph[7] = {3};
    // 4 <-> 5
    graph[4].emplace_back(5);    // graph[4] = {2,5};
    graph[5].emplace_back(4);    // graph[5] = {2,4};
    // 6 <-> 7
    graph[6].emplace_back(7);    // graph[6] = {3,7};
    graph[7].emplace_back(6);    // graph[7] = {3,6};
    
    dfs(1); // 1, 2, 3, 6, 7, 4, 5

    return 0;
}

DFS 구현(스택) - 재귀와는 다르게 후입선출 개념으로 마지막 삽입된 노드 기준으로 깊이우선탐색을 함

1. 방문 리스트에 시작 노드 기록

2. stack에 시작 노드의 인접 노드 삽입(push)

3. stack에서 노드를 pop하면서 방문 처리(출력)

4. 꺼낸 노드와 이웃한 노드를 stack에 삽입(push), 방문했던 노드인지 체크

5. stack에 아무것도 남지 않을 때까지 2~4 반복

6. 모든 노드를 방문할 때까지 1~5반복

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int number = 7;	      // 노드 개수
bool visited[8];      // 방문 리스트
vector<int> graph[8]; // 연결된 숫자를 넣기 위해 배열을 8개 만듬

vector<int> v;

// 스택
void dfs(int node)
{
    // 시작 노드 삽입
    v.emplace_back(node);
    
    while(!v.empty())		// 비어있지 않다면
    {
        int next = v.back();  // 마지막 노드를 반환해서 변수에 넣음
        v.pop_back();		// 꺼냄
        
        if(!visited[next])	// 방문 처리가 되어있으면
        {
            visited[next] = true;   // 방문 처리
            cout << next << " ";    // 경로 출력

            for(int i = 0; i < graph[next].size(); i++)
            {
            	int n = graph[next][i];
                if(visited[n] == false)  // 방문 전
                {
                    v.emplace_back(n);	// 다음 노드를 넣음
                }
            }
        }
    }
}

int main()
{
    // 1 <-> 2
    graph[1].emplace_back(2);    // graph[1] = {2};
    graph[2].emplace_back(1);    // graph[2] = {1};
    // 1 <-> 3
    graph[1].emplace_back(3);    // graph[1] = {2,3};
    graph[3].emplace_back(1);    // graph[3] = {1};
    // 2 <-> 3
    graph[2].emplace_back(3);    // graph[2] = {1,3};
    graph[3].emplace_back(2);    // graph[3] = {1,2};
    // 2 <-> 4
    graph[2].emplace_back(4);    // graph[2] = {1,3,4};
    graph[4].emplace_back(2);    // graph[4] = {2};
    // 2 <-> 5
    graph[2].emplace_back(5);    // graph[2] = {1,3,4,5};
    graph[5].emplace_back(2);    // graph[5] = {2};
    // 3 <-> 6
    graph[3].emplace_back(6);    // graph[3] = {1,2,6};
    graph[6].emplace_back(3);    // graph[6] = {3};
    // 3 <-> 7
    graph[3].emplace_back(7);    // graph[3] = {1,2,6,7};
    graph[7].emplace_back(3);    // graph[7] = {3};
    // 4 <-> 5
    graph[4].emplace_back(5);    // graph[4] = {2,5};
    graph[5].emplace_back(4);    // graph[5] = {2,4};
    // 6 <-> 7
    graph[6].emplace_back(7);    // graph[6] = {3,7};
    graph[7].emplace_back(6);    // graph[7] = {3,6};
    
    dfs(1); // 1, 3, 7, 6, 2, 5, 4

    return 0;
}

 

BFS(너비 우선 탐색)

; 루트 노드(혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

  노드가 적은 그래프를 순회하거나 최단경로를 탐색할 때 사용한다.

  최대한 넓게 이동한 다음 더 이상 갈 수 없을 때 아래로 이동한다.

  큐를 이용해서 구현한다.

 

대표적 문제 유형

1. 경로탐색 유형(최단거리, 시간)

2. 네트워크 유형(연결)

3. 조합 유형(모든 조합 만들기)

 

활용 유형

1.그래프의 모든 노드를 순환해야 하는 경우 -> DFS, BFS 둘다 사용 

2. 이전 경로의 정보가 필요한 경우 -> DFS 사용(BFS는 경로의 정보를 못가짐)

3.  최단거리를 구해야 하는 경우 -> BFS 사용