[Algorithm] DFS 구현하기

DFS : Depth - First Search (깊이 우선 탐색)

• 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다.
• 넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다.
• stack 또는 recursive(재귀 함수)로 구현할 수 있다.

---

🏷️ 변수 설명

그래프를 구현하는 방법에는 두 가지 방법이 있다.

1. 인접 리스트 (상대적으로 효율적)
2. 인접 행렬 (직관적 but 비효율적)

1. int v, e

v : 정점의 개수

e: 정점 사이를 잇는 간선의 개수

입력받은 정보를 통해 인접 리스트와 방문 여부를 저장하는 변수의 크기를 할당할 수 있다.

 

2. vector<vector<int>> graph

이중 vector를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있으며, 유동적으로 사용이 가능하다.

먼저 정점의 개수를 입력받은 후 .assign()함수를 이용해서 필요한만큼 할당한다.

// assign 함수를 통해서 vector<int>를 v+1개 할당
graph.assign(v + 1, vector<int>(0, 0));

 

이후 간선이 연결하는 두 정점을 입력 받으면서, 간선 정보를 graph에 입력한다. (양방향 간선 구현)

int s, e;
cin >> s >> e; // s : 2, e : 5 일 때
graph[s].emplace_back(e); // graph[2].emplace_back(5);
graph[e].emplace_back(s); // graph[5].emplace_back(2);

 

graph[].emplace_back()

백터의 마지막 부분에 새로운 요소 추가(move로 인해 복사생성자 X)

push_back() 과 emplace_back()의 차이점

• push_back()은 함수를 넣는 과정에서 복사생성자를 호출
• insert를 하게되면 모든 값들을 새로운 메모리에 복사한 후 해당 자리에 값을 넣는다.
• 결론적으로 복사생성자로 인한 오버헤드가 커지며 성능 저하를 야기한다.
• 해결책 : emplace(), emplace_back()

 

3. vector<bool> visited

각 노드를 방문했는지의 여부를 저장하는 변수이다.

vector로 선언한 이유는 정점의 개수를 입력 받아서 정점의 개수만큼만 메모리 할당하기 위해서이다.

이렇게 하면 배열의 크기를 미리 크게 정해놓지 않아도 되기 때문에 메모리 공간을 절약할 수 있다.

// 노드는 1번부터 v번까지이고, 아직 어떤 노드도 방문하지 않았기 때문에 false로 초기화
visited.assign(v + 1, false);

 

만약 리스트로 저장하고 싶으면 아래와 같이 사용하면 된다.

bool visited[9];

 

🏷️ 코드 예시

[Parameters]

int v, e; // 정점의 개수, 간선의 개수
vector<vector<int>> graph; // 인접 리스트
vector<bool> visited; // 정점 방문 여부 저장

 

[Method]

void input(){
    cin >> v >> e;
    // 메모리 공간 할당 및 초기화
    graph.assign(v + 1, vector<int> (0, 0));
    isVisited.assign(v + 1, false);
    
    for(int i = 0; i < e; i++){
    	int s, e;
        cin >> s >> e;
        // 양방향 간선을 연결시킨다.
        graph[s].emplace_back(e);
        graph[e].emplace_back(s);
    }
}

// DFS 함수 
void dfs(int x)
{
    visited[x] = true;
    cout << x << " "; // 방문한 노드 출력
    
    // 현재 정점과 간선으로 연결되어 있는 모든 정점들을 둘러본다.
    for (int neighbor : graph[x])
    {   // 만일 방문하지 않았다면 매개변수로 전달하여 DFS를 재귀적으로 호출한다.
        if (!visited[neighbor])
        {
            dfs(neighbor);
        }
    }
}