23.07.13 스터디, 깊이 우선 탐색 알고리즘 학습
DFS (deepth-first-search) 깊이 우선 탐색
트리나 그래프에서 사용되는 탐색 알고리즘입니다. 이 방법은 시작 정점에서 시작하여 각 분기점에 대해 최대한 깊이 들어가면서 탐색하고, 더 이상 진행할 수 없게 되면 이전 분기점으로 돌아와서 다른 경로를 탐색하는 방식으로 진행됩니다.
주로 스택 또는 재귀를 이용하여 구현됩니다.
DFS는 많은 문제 해결에서 사용되며, 그래프가 사이클을 포함하지 않는 경우 적합합니다.
그래프가 넓고 노드 수가 많을 경우,
DFS는 탐색 과정에서 불필요한 방향으로 깊이 들어가기 때문에 시간이 오래 걸릴 수 있습니다. 이런 경우에는 BFS(Breadth-First Search, 너비 우선 탐색)와 같은 다른 알고리즘을 사용할 수 있습니다.
쉽게 설명하면, 이제 말하는 것이 dfs가 돌아가는 로직이라고 생각하시면 됩니다. 좌측부터 채워지며, 아래까지 쭈욱 채우고, 이후 옆으로 옮겨가서 채워주고, 이런식으루 좌->우로 옮겨가며 최하단의 노드까지 채워주면 끝이 되는 것입니다.
이해하기 쉽게 간결히 정리하면
- 알고리즘 원리
- DFS는 방문한 노드를 표시하고 현재 노드에서 갈 수 있는 인접 노드를 찾습니다.
인접 노드가 없거나 방문한 노드일 경우, 앞에서 방문한 노드로 되돌아갑니다.
이러한 과정을 반복하며 그래프를 탐색합니다.
결국, 모든 경로를 방문하게 됩니다.
- 구현 방법
DFS는 재귀와 스택을 이용한 방법으로 구현할 수 있습니다.
- 재귀(recursion): 현재 노드를 방문하고, 인접 노드에 대해 아직 방문하지 않은 노드가 있다면 그 노드를 기준으로 다시 DFS를 호출합니다. 재귀호출은 노드가 방문한 순서와 깊이를 기억할 수 있는 명시적인 스택을 사용하지 않으므로 코드가 간결하다는 장점이 있습니다.
- 스택(stack): 현재 노드를 방문하고 스택에 삽입합니다. 인접 노드 중 방문하지 않은 노드가 있다면 그 노드를 스택에 삽입하고 현재 노드로 설정합니다. 만약 인접 노드 중 방문하지 않은 노드가 없다면, 스택에서 최상위 노드를 뽑아 뒤로 돌아가기 위해 사용합니다.
- 시간 복잡도 DFS의 시간 복잡도는 그래프의 타입과래프를 나타내는 방식에 따라 다릅니다.
- 인접 행렬 (Adjacency Matrix) 연산: O(V^2), 여기서 V 정점의 수입니다.
- 인접 리스트 (Adjacency List) 연산: O(V+E), 여기서 E는 간선의 수입니다.
- DFS를 사용하는 대표적인 예시입니다.
DFS는 다양한 문제에 적용됩니다.
예를 들어, 미로 찾기, 연결 요소 찾기, 사이클 판별, 최단 경로 찾기, 최소 신장 트리(Min Spanning Tree) 찾기 등이 있습니다. - 단점과 대안
DFS는 방문 노드 수가 많거나 그래프가 넓을 때, 시간이 오래 걸릴 수 있습니다 이 경우 BFS(Breadth-First Search, 너비 우선 탐색)를 사용하면, 효과적인 탐색이 가능합니다.
BFS는 주변 노드를 모두 방문한 후, 그 다음 레벨의 노드로 넘어갑니다.
이러한 방식으로 그래프를 탐색하는데, 전체 탐색간이 효율적으로 단축되기 때문에 넓은 그래프에 적절한 선택지가 됩니다.
DFS 핵심이론
DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로, 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 보통 인접 리스트로 표현합니다. 그리고 DFS의 탐색 방식은 후입선출(스택)의 특성을 가지므로 스택을 사용하는 경우가 종종 있습니다.
BUT, 필자는 편의를 위해 스택으로 예시를 들었으나, DFS 구현은 스택보다는 스택의 성질을 갖고 있는 재귀함수로 많이 구현합니다. 즉, 대부분의 DFS는 재귀 함수로 구현 합니다.
(스택의경우) 로직
- DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 해야합니다.
- 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입합니다.
- 스택 자료구조에 값이 없을 때까지 반복합니다.
참고,
위 그림을 보시면 조금 더 이해하기 쉬울 것입니다. 간선이 이렇게 연결되어 있을경우엔 다르게 작용하는 것입니다.
1. 스택의 최상단 노드를 확인해야합니다.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고,
방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 제거합니다.
코드로 확인
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class DFSUsingStack {
static boolean[] visited = new boolean[8];
static List<List<Integer>> graph = new ArrayList<>();
public static void main(String[] args) {
initializeGraph();
dfs(1);
}
private static void initializeGraph() {
for (int i = 0; i < 8; i++) {
graph.add(new ArrayList<>());
}
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(2).add(1);
graph.get(2).add(4);
graph.get(2).add(5);
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(6);
graph.get(4).add(2);
graph.get(4).add(3);
graph.get(4).add(5);
graph.get(4).add(7);
graph.get(5).add(2);
graph.get(5).add(4);
graph.get(5).add(7);
graph.get(6).add(3);
graph.get(6).add(7);
graph.get(7).add(4);
graph.get(7).add(5);
graph.get(7).add(6);
}
private static void dfs(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
visited[start] = true;
System.out.print(start + " ");
while (!stack.isEmpty()) {
int currentNode = stack.peek();
List<Integer> adjNodes = graph.get(currentNode);
boolean hasUnvisitedNode = false;
for (Integer node : adjNodes) {
if (!visited[node]) {
stack.push(node);
visited[node] = true;
System.out.print(node + " ");
hasUnvisitedNode = true;
break; // 들어갔으니 중지한다
}
}
if (!hasUnvisitedNode) {
stack.pop();
}
}
}
}
