Goal

• DFS를 설명할 수 있다.
• DFS를 구현할 수 있다.
• DFS 응용 문제를 찾고 풀 수 있다.

DFS

DFS는 깊이우선탐색 (Depth-First Search)으로 이름에서 유추할 수 있듯이 깊이를 먼저 탐색하는 방법이다.

BFS와 함께 그래프의 대표적인 탐색방법이므로 이를 이해하기 위해 먼저 그래프가 뭔지 부터 살펴보자.

그래프

그래프의 대표적인 정의는 정점과 간선의 집합이다. 쉽게 말해 점과 선으로 이루어져 있는 모양을 떠올리면 된다. 간선은 다른 정점과 연결할 수 있고 자신과 연결할 수도 있으며 방향이 있을 수도 없을 수도 있다. 간선마다 가중치가 부여될 수도 있다.

이러한 특성에 따라 무방향 그래프, 방향그래프, 가중치 그래프 등 다양한 이름의 그래프가 될 수 있다.

다음은 대표적인 그래프의 모습인데 정점의 집합을 보통 V 간선의 집합을 E로 표현한다.

또한 각 정점마다 차수(degree)가 존재하는데 이는 각 정점에 연결된 간선의 개수를 말한다. 위의 예에서 1번 정점의 차수는 2, 4번 정점의 차수는 3과 같은 식이다. 정점은 흔히 노드(Node)라고도 부른다.

간선 하나를 거쳐 A와 B로 갈 수 있을 때 이를 인접하다(adjacent)고 한다. 무방향 그래프에서는 당연히 A와 B, B와 A가 인접하지만, 방향 그래프에 따라서 어느 한쪽만이 인접할 수 있다.

간선을 따라가다 보니 시작한 정점으로 돌아오는 경로를 싸이클(cycle)이라고 한다.

여기서는 DFS에 대해 공부하기 위함이기에 그래프는 이정도로 간략하게만 살펴보도록 하자.

DFS

이러한 그래프를 깊이있게 탐색하는 방법이 바로 DFS이다. DFS는 백트레킹 방식을 사용하는데 즉, 한 방향으로 깊에 맨 끝까지 갔다가 끝을 보면 다시 돌아오는 방법이다. 예를 통해 알아보자.

5개의 정점을 가진 그래프가 있을 때 다음과 같이 탐색하는 것이 바로 DFS이다. 가장 먼저 왼쪽으로 쭉 내려가서 끝인 4를 만나면 다시 2로 올라와 탐색하지 않은 방향을 마저 탐색하고 끝나면 다시 1로 올라와서 탐색하지 않은 방향을 탐색하는 것이다.

이쯤되면 DFS가 어떤 방식인지는 알았을 것이다. 하지만 그래서 어떻게 구현할건데?

구현

DFS는 접시를 쌓듯 차곡차곡 쌓는 Stack의 원리를 사용해 구현할 수 있다.

우선 시작 노드를 스택에 넣고 방문처리 한 후 시작한다. 그 이후에 다음의 알고리즘을 따른다.

1. 스택의 최상단 노드를 확인한다.
2. 해당 노드에 방문하지 않은 인접한 노드가 있다면 방문처리하고 스택에 넣는다.
3. 방문하지 않은 인접노드가 없다면 노드를 스택에서 뺀다.

이를 반복해주면 된다.

다음을 위의 예에 적용해보면,

시작 // 1 방문처리, 스택: 1

스택: 1 / 최상단 노드: 1 / 1의 방문하지 않은 인접한 노드: 2, 3 / 방문처리: 1 - 2

스택: 1, 2 / 최상단 노드 : 2 / 2의 방문하지 않은 인접한 노드: 4, 5 / 방문처리: 1 - 2 - 4

스택: 1, 2, 4 / 최상단 노드: 4 / 4의 방문하지 않은 인접한 노드: 없음 → 4를 뺀다 / 방문처리: 1 - 2 - 4

스택: 1, 2 / 최상단 노드: 2 / 2의 방문하지 않은 인접한 노드: 5 / 방문처리: 1 - 2 - 4 - 5

스택: 1 / 최상단 노드: 1 / 1의 방문하지 않은 인접한 노드: 3 / 방문처리: 1 - 2 - 4 - 5 - 3

이제 다음은 이 알고리즘을 그대로 코드로 옮기면 된다. 기본적으로 프로그램은 Stack구조를 사용하기 때문에 따로 Stack을 구현하지 않고 재귀 형태로 구현할 수 있다.

    #include<iostrea>
    #include<vector>
    
    vector<int> node[5];
    int visited[5];
    
    int dfs(int v) {
    	// 이미 방문 했다면 return;
    	if (visited[v]) return;
    	
    	// 방문 표시하고 출력.
    	visited[v] = true;
    	cout<<v<<"\n";
    
    	for(int i=0; i<node[v].size(); i++) {
    		int n = node[v][i];
    		dfs(n);
    	}
    }
    
    int main(void) {
    	node[1].push_back(2);
    	node[1].push_back(3);
    
    	node[2].push_back(4);
    	node[2].push_back(5);
    
    	node[3].push_back(1);
    	
    	node[4].push_back(2);
    
    	node[5].push_back(2);
    
    	dfs(1);
    
    	return 0;
    }

참고

라이님 블로그

안경잡이 개발자 블로그