⭐️ DFS : Depth-First Search (깊이 우선 탐색) 이란?
[출처 : https://en.wikipedia.org/wiki/Depth-first_search]
- 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다.
- 넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다.
- stack 또는 recursive(재귀 함수)로 구현할 수 있다.
⭐️ DFS의 특징
- 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다.
정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다.
- 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2)
- 재귀 함수로 구현 시, 별도의 자료구조가 필요하지 않으므로 메모리를 아낄 수 있다.
(BFS의 경우 queue를 사용해야 하므로 DFS에 비해 메모리를 더 사용할 수 밖에 없다.)
- 얻은 결과가 최단 경로라는 보장이 없다. (반면, BFS는 얻은 결과가 최단 경로이다.)
⭐️ 변수 설명
그래프를 구현하는 방법에는 인접 리스트를 사용하는 방법과 인접 행렬을 사용하는 방법이 있다.
인접 행렬로 구현하는 방식은 좀 더 직관적이나 시간 복잡도나 공간 복잡도 면에서 비효율적이기 때문에, 인접 리스트로 구현할 것이다.
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);
3. vector<bool> isVisited
각 노드를 방문했는지의 여부를 저장하는 변수이다.
vector로 선언한 이유는 정점의 개수를 입력 받아서 정점의 개수만큼만 메모리 할당하기 위해서이다.
이렇게 하면 배열의 크기를 미리 크게 정해놓지 않아도 되기 때문에 메모리 공간을 절약할 수 있다.
// 노드는 1번부터 v번까지이고, 아직 어떤 노드도 방문하지 않았기 때문에 false로 초기화
isVisited.assign(v + 1, false);
⭐️ DFS 진행 단계
1. DFS를 시작할 노드를 정해서 매개변수로 전달한다.
2. 전달 받은 매개변수가 현재 노드이므로, 현재 방문 중인 노드를 방문처리 해준다. (isVisited[cur] = true)
3. 현재 노드와 인접한 노드들을 반복문을 통해 하나씩 접근한다. 해당 노드를 다음 노드(next)로 설정한다.
4. 다음 노드(next)를 이전에 방문했는지 확인한다.
만일 방문했다면 다시 방문할 필요가 없으므로 지나간다. ( continue 문 )
만일 아직 방문하지 않았다면 DFS를 재귀적으로 호출한다. ( DFS(next); )
5. 2~4번을 더 이상 방문할 노드가 없을 때 까지 반복한다.
⭐️ 재귀적으로 DFS 실행하기
위와 같은 그래프가 있다고 가정했을 때, 이중 vector graph에 간선 정보를 저장해보자.
for(int i = 0; i < e; i++){
int s, e;
cin >> s >> e;
graph[s].emplace_back(e);
graph[e].emplace_back(s);
}
위의 코드로 정보를 입력할 수 있는데, 간선은 두 정점을 잇기 때문에 두 정점이 무엇인지 입력 받은 후에 정보를 입력한다.
graph[시작 정점].emplace_back(도착 정점)의 형식을 띄는데, 시작 정점 -> 도착 정점으로 이어진 간선이 있다는 뜻이다.
그렇게 정보를 입력하고 나면 그림2처럼 graph가 형성이 되었을 것이다.
이제 1을 시작 정점으로 설정하고 한 단계만(그림3까지) DFS를 실행해보자.
1) 우선 isVisited[1] = true를 하여 방문 체크한다.
2) 이후 1과 간선으로 연결된 정점들을 확인하는데, graph[cur]에 있는 모든 요소. 즉, 정점들을 확인하면 된다.
for(int i = 0; i < graph[cur].size(); i++){
int next = graph[cur][i];
if(!isVisited[next]){
DFS(next);
}
}이를 위해 반복문을 이용하는데, graph[cur]도 vector<int>이기 때문에 size() 함수를 이용해서 graph[cur]에 들어있는 모든 원소들을 순회한다.
graph[cur][i] (이 경우에는 2)를 다음에 방문할 정점(next)으로 설정하고, 해당 정점을 방문하지 않았을 때에만 DFS를 재귀적으로 호출한다.
3) DFS를 호출하게 되면 2)에서 매개변수로 전달했던 next가 cur (이 경우에는 2)로 설정된다.
따라서 isVisited[2] = true를 하여 방문했다고 체크한다.
이후 2과 간선으로 연결된 정점들을 반복문을 통해 확인한다. 이 때, graph[2]를 보면 요소로 1, 4, 5가 들어있는데,
1은 이미 isVisited[1] = true이기 때문에 DFS를 실행하지 않고, 넘어간다.
다음으로 4를 확인하는데 4는 방문한 적이 없으므로 isVisited[4] = false이고, 따라서 2)에서처럼 DFS를 재귀적으로 호출한다.
4) DFS를 호출했으므로 cur이 4로 설정되어 있다.
isVisited[4] = true를 하여 방문했다고 체크한다.
이후 4와 간선으로 연결된 정점들을 반복문을 통해 확인한다. 이 때, graph[4]를 보면 요소로 2가 있는데, isVisited[2] = true이므로 DFS를 실행하지 않고, 모든 요소를 확인했기 때문에 반복문을 마치게 된다.
여기까지 진행을 했으면, 방문한 노드는 1, 2, 4가 될 것이다. [그림3과 같은 상태일 것이다.]
이로써 DFS가 한 단계 완료되었다. 이제 4에서 더 이상 방문할 정점이 없기 때문에 방문할 정점이 있는 2로 돌아간다.
정확히는 4)에서의 DFS(cur이 4)가 종료되고 3)에서의 DFS(cur이 2)로 돌아간다.
이제 위에서 설명했던 방법을 graph 전체를 다 돌아볼 때까지 반복하면 된다.
ⓐ 2번 정점에서 5로 이동,
ⓑ 5번 정점에서 2는 방문했으므로 pass, 6은 아직 방문하지 않았으므로 6으로 이동
ⓒ 6번 정점에서 5는 이미 방문했으므로 pass. DFS 종료
ⓓ ⓑ의 DFS로 되돌아옴. 하지만 더 방문할 정점이 없으므로 DFS 종료
ⓔ ⓐ의 DFS로 되돌아옴. 하지만 더 방문할 정점이 없으므로 상위 DFS로 이동.
위의 과정을 마치면 그림4와 같은 상태가 될 것이다.
현재 정점이 1로 설정되어 있는 상태일텐데, 이제 1번 정점과 인접한 정점들 중 방문해야 할 정점은 3이다.
따라서 3번 정점으로 이동한다. (3번 정점은 아직 방문하지 않았기 때문)
3번 정점과 인접한 정점 1번은 이미 방문했기 때문에 DFS가 종료되고,
제일 처음 실행했던 즉, cur이 1인 DFS도 모든 정점을 방문했기 때문에 DFS가 비로소 완전히 종료된다.
⭐️ Code
[Parameters]
int v, e; // 정점의 개수, 간선의 개수
vector<vector<int>> graph; // 인접 리스트
vector<bool> isVisited; // 정점 방문 여부 저장
[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);
}
}
void DFS(int cur){
isVisited[cur] = true;
cout << "방문한 노드 : " << cur << '\n';
// 현재 정점과 간선으로 연결되어 있는 모든 정점들을 둘러본다.
for(int i = 0; i < graph[cur].size(); i++){
int next = graph[cur][i];
// 만일 방문하지 않았다면 매개변수로 전달하여 DFS를 재귀적으로 호출한다.
if(!isVisited[next]){
DFS(next);
}
}
}