DFS
DFS ?
- 그래프 완전 탐색이 필요할 때, 즉 모든 노드를 방문해야 할 때 DFS를 주로 사용한다.
- 말 그대로 그래프의 시작 노드에서 탐색할 분기를 하나 정하게 되면 그 분기의 최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여 다시 최대 깊이까지 탐색을 수행하는 알고리즘이다.
- Stack과 재귀함수를 이용하여 구현한다.
💡 DFS 핵심 개념 - 방문 여부 체크
- DFS는 한 번 방문한 노드를 재방문하면 안되기 때문에, 각각의 노드에 대한 방문 여부를 체크할 수 있는 배열이 필요하다 !
💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도
노드의 수 = V, 간선의 수 = E
- 인접 리스트를 이용한 방법 - O(V + E)
- 모든 노드 방문 - O(V) → DFS는 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.
- 간선 탐색 - O(E) → 각 노드에서 해당 노드와 연결된 모든 간선을 하나씩 탐색하기 때문에 O(E) 시간 복잡도가 요구된다.
<aside> 💡
인접 리스트란 ?
- 각 노드마다 해당 노드에 연결된 간선 정보를 2차원 배열로 저장하는 방식이다.
ex: 노드 1: [2, 5] → 노드 1에 노드 2, 5가 연결되어 있다.
</aside>
- 인접 행렬를 이용한 방법 - O(V^2)
- 모든 노드 방문 - O(V) → 인접 리스트 구현 방식과 동일하게 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.
- 간선 탐색 - O(V) → 인접 행렬에선 노드간 연결 여부를 확인하기 위해선 모든 노드 쌍을 확인해야 하기 떄문에 O(V) 시간 복잡도가 요구된다.
<aside> 💡
인접 행렬이란 ?
- 노드 간의 연결 관계를 2차원 배열로 저장하는 방식이다.
ex: matrix[u][v] = 1 → 노드 u, v를 연결하고 있는 가중치값이 1인 간선 정보
</aside>
💡 DFS 핵심 개념 - Stack vs 재귀 함수
- 두 방식 사이에 장단점이 있는 것은 아니고, DFS를 구현할 때 Stack을 이용하는 방식과 재귀 함수를 이용하는 방식이 있는 것이다.
- DFS 구현 - Stack
- Stack을 사용하는 방식은 당연히 **후입선출(LIFO)**을 따른다.
public static void DFS(int v){
Stack<Integer> stack = new Stack<>();
stack.push(v);;
while(!stack.isEmpty()){
int cur = stack.pop();
visited[cur] = true;
procedure.add(cur);
// 해당 노드의 인접리스트를 검사하며, visited가 false인 경우에만 stack.push
for (int i : graph[cur]) {
if(!visited[i]){
stack.push(i);
}
}
}
}
- DFS 구현 - 재귀 함수
- 재귀함수를 사용하는 경우엔 당연히 무한 루프로 인해 Stack Overflow가 발생하지 않도록 주의해야 한다 !
static void DFS(int v){
// 방문배열이 true면 return
if(visited[v]) return;
// v 노드에 방문했으므로, 해당 방문배열을 true로 바꿔주고, 탐색순서 리스트에 추가해줌
visited[v] = true;
procedure.add(v);
// 해당노드의 ArrayList(인접노드)를 모두 돌며 방문배열이 false인 경우에
for(int i : graph[v]){
if(!visited[i]){
DFS(i); // 해당 노드에 대해서 DFS를 다시 실행한다.
}
}
}
문제: 연결 요소의 개수 (백준 11724)
문제 링크
알고리즘 [접근 방법]
- 스택 혹은 재귀 함수를 이용하여 구현한 DFS를 이용해 모든 노드를 방문하고 방문 여부를 체크한다.
해결 코드
- 각 노드에 대한 방문 여부는 visited 배열에 저장해두어 체크하면 된다. → 방문한 노드들의 개수를 카운트해서 더해주면 결과값이 된다.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static int N, M;
static List<List<Integer>> graph;
static boolean[] visited;
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visited = new boolean[N + 1];
list = new ArrayList<>();
for (int i = 0; i <= N; i++) {
list.add(new ArrayList<>());
}
for (int i = 1; i <= M; i++) {
int u = input.nextInt();
int v = input.nextInt();
list.get(u).add(v);
list.get(v).add(u);
}
int count = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfsStack(i);
count++;
}
}
System.out.println(count);
}
//재귀를 이용한 DFS
static void dfs(int n) {
visited[n] = true;
for (int i = 0; i < graph.get(n).size(); i++) {
int neighbor = graph.get(n).get(i);
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
// 스택을 사용한 DFS
static void dfsStack(int n) {
Stack<Integer> stack = new Stack<>();
stack.push(n);
visited[n] = true;
while (!stack.isEmpty()) {
int current = stack.pop();
for (int i = 0; i < graph.get(current).size(); i++) {
int neighbor = graph.get(current).get(i);
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
}
}
정리
- 문제를 봤을 때 그래프의 깊이를 생각하고, Stack Overflow가 발생할지에 따라 DFS를 Stack으로 구현할지, 재귀함수로 구현할지를 판단하자 !
https://thin-azimuth-2a9.notion.site/GDG-DFS-13cf4ee21c0080279529f70ade160e94?pvs=4
GDG 스터디 - DFS를 이용한 연결 요소 개수 찾기 | Notion
DFS
thin-azimuth-2a9.notion.site
