깊이 우선 탐색

1. 개요

2. 상세

3. 장단점

3.1. 장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

3.2. 단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

4. 소스 코드

4.1. C++

#!syntax cpp
const int MAX = 100'001;

bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void dfs(const vector<int> graph[], int current) { // graph는 인접 리스트, current는 현재 노드
    visited[current] = true; // current 방문

    for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자.
        if(!visited[next]) { // 만일 next에 방문하지 않았다면
            dfs(graph, next); // next 방문
        }
    }
}

4.2. Python

#!syntax python
def dfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    def search(current:int): # 재귀함수 정의
        visited[current] = True # current 방문
        for nxt in graph[current]: # current의 인접 노드를 확인한다. 이 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                search(nxt) #nxt 방문
    search(start)

5. DFS 트리

• Tree edge란 DFS중 a정점을 방문한 후 b정점을 처음 방문할 때, a→b의 유향간선을 말한다.

• Back edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, b가 a의 조상일 때 a→b의 유향간선을 말한다,

• Forward edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a가 b의 조상일 때 a→b의 유향간선을 말한다.

• Cross edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a→b의 유향간선이 Back edge나 Forward edge가 아닌 경우를 말한다.