DFS(Depth-First Search) : 깊이 우선 탐색
- 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다.
- 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후,
다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. - 재귀함수 또는 Stack 자료구조를 이용한다.
- 재귀함수를 이용하므로 stack overflow에 유의해야 한다.
스택 오버플로우(stack overflow)
스택 오버 플로우는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다.
1. 시간복잡도
시간복잡도(노드 수: N, 에지 수 E)
- O(N+E)
- 모든 노드를 한번씩 방문하고, 모든 에지를 한번씩 검사하기 때문에 V+E라고 할수 있다.
이 글에선 인접리스트로 표현하는 경우만 다뤘지만, 인접 행렬로 표현하는 방법도 있다.
인접 행렬로 표현하면 시간복잡도는 O(N^2)가 된다.
2. DFS 핵심 이론
1) 방문여부 확인용 배열
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| T | F | F | F | F | F |
- DFS는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
( 이부분이 제대로 되지 않으면 , 재귀함수로 인해 무한루프에 빠질 수 있으니 조심해야 한다. ) - 예를들어 1~6의 노드를 가진 그래프가 있으면,
boolean[] arr = new boolean[7];으로 배열을 만들어 준다.
( 0번 인덱스는 사용하지 않는다. ) - 해당 노드를 방문하면 해당 인덱스의 값을 TRUE로 바꿔준다.
2) 원본 그래프 -> 자료구조 초기화(인접리스트)
- 시작할 노드를 정한다.
- 각 노드에서 갈수있는 다른 노드를 확인 후 인접리스트로 초기화 한다.
- 시작점을 정했기 때문에 시작점의 방문배열을 T로바꿔주고, 스택에 시작점을 더한다.
3) 스택(재귀함수)에서 꺼낸 노드의 인접노드를 스택에 삽입
- 맨 처음에 넣었던 시작노드 1을 스택에서 pop 한다. ( pop 할때, 해당 값의 방문배열은 T로 변경 )
- 1의 인접노드 2,3을 스택에 삽입한다.
- 이 과정을 스택이 비워질 때까지 반복한다.
4) 반복
(편의를 위해 pop() 괄호 안에 값을 넣도록 하겠다.)
1. 위에서 1이 pop되고, 2,3이 스택에 들어있는 상황이다.
2. pop(3) -> 3의 방문배열 True -> 3의 인접노드 push(4)
3. pop(4) -> 4의 방문배열 True -> 4의 인접노드 push(6)
4. pop(6) -> 6의 방문배열 True -> 6은 인접노드가 없기 때문에 push할 노드는 없다.
5. pop(2) -> 2의 인접노드는 5,6이지만 6의 방문배열은 True 이므로 push(5)만 할수 있다.
6. pop(5) -> 5의 방문배열 True
7. stack.isEmpty() == true
- 마지막으로 pop(5)를 하고 나니, 스택이 비워졌다. -> 반복 종료
- 결과적으로 탐색 순서는 [ 1 - 3 - 4 - 6 - 2 - 5 ]이다.
3. 재귀함수
실제로는 스택보다는 재귀함수를 이용해서 구현하는 경우가 많다.
재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.
4. 구현
static boolean[] visited = new boolean[7]; //방문 배열
static ArrayList<Integer>[] A = new ArrayList[7];//ArrayList타입 배열
static ArrayList<Integer> procedure = new ArrayList<>(); //탐색 순서 list
public static void main(String[] args){
for(int i=1;i<=6;i++) {
A[i] = new ArrayList<>();//배열의 각 요소마다 ArrayList를 가진다.
}
//예제에서 노드1의 경우 3이 먼저,
//노드2의 경우 6이 먼저 실행하기 때문에 순서를 바꿔줌
A[1].add(3);
A[1].add(2);
A[2].add(6);
A[2].add(5);
A[3].add(4);
A[4].add(6);
//1번노드에서 DFS 실행
DFS(1);
System.out.println(procedure.toString()); // [1, 3, 4, 6, 2, 5]
}
static void DFS(int v){
//방문배열이 true면 return
if(visited[v]) return;
//v 노드에 방문했으므로, 해당 방문배열을 true로 바꿔주고, 탐색순서 리스트에 추가해줌
visited[v] = true;
procedure.add(v);
//해당노드의 ArrayList(인접노드)를 모두 돌며 방문배열이 false인 경우에
for(int i : A[v]){
if(!visited[i]){
DFS(i); //해당 노드에 대해서 DFS를 다시 실행한다.
}
}
}
(출처) Do it! 알고리즘 코딩 테스트 자바 편 e-book
http://www.yes24.com/Product/Goods/108571508
Exciting dev life / 댓글, 피드백, 질문 환영합니다 !!!