깊이 우선 탐색(DFS) 알고리즘
DFS(Depth-First Search) : 깊이 우선 탐색
DFS(Depth-First Search)는 그래프 전체를 탐색하는 방법(i.e., 완전 탐색) 중 하나로, ‘깊이’를 우선적으로 탐색하는 알고리즘이다.
DFS는 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.
예를 들어, DFS 알고리즘은 미로 탐색 시 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법이다.
특히 그래프에서 간선이나 변수 정보를 수시로 변경해야 하는 문제는 DFS를 활용하는 것이 효과적이다.
DFS 동작 과정
DFS(Depth-First Search)는 재귀함수 또는 Stack 자료구조를 이용한다.
재귀함수를 이용하므로 stack overflow에 유의해야 한다.
스택 오버플로우(stack overflow)
지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다.
DFS 기본 동작 방식
1. 방문여부 확인용 배열
DFS는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
( 이부분이 제대로 되지 않으면 , 재귀함수로 인해 무한루프에 빠질 수 있으니 조심해야 한다. )
예를들어 1~6의 노드를 가진 그래프가 있으면, boolean[] arr = new boolean[7]; 으로 배열을 만들어 준다.
( 0번 인덱스는 사용하지 않는다. )
해당 노드를 방문하면 해당 인덱스의 값을 TRUE로 바꿔준다.
2. 원본 그래프 -> 자료구조 초기화(인접리스트)
시작할 노드를 정한다.
각 노드에서 갈수있는 다른 노드를 확인 후 인접리스트로 초기화 한다.
시작점을 정했기 때문에 시작점의 방문배열을 T로바꿔주고, 스택에 시작점을 더한다.
3. 스택(재귀함수)에서 꺼낸 노드의 인접노드를 스택에 삽입
맨 처음에 넣었던 시작노드 1을 스택에서 pop 한다.
1의 인접노드 2,3의 방문 상태를 확인한 후 방문하지 않았으면 스택에 삽입한다.
이 과정을 스택이 비워질 때까지 반복한다.
4. 반복
위에서 1이 pop되고, 2,3이 스택에 들어있는 상황이다.
pop(3) -> 3의 인접노드 push(4) -> 4의 방문배열 True
pop(4) -> 4의 인접노드 push(6) -> 6의 방문배열 True
pop(6) -> 6은 인접노드가 없기 때문에 push할 노드는 없다.
pop(2) -> 2의 인접노드는 5,6이지만 6의 방문배열은 True 이므로 push(5)만 할수 있다. -> 5의 방문배열 True
pop(5) -> 스택이 비워졌다. -> 반복 종료
결과적으로 탐색 순서는 [ 1 - 3 - 4 - 6 - 2 - 5 ]이다.
DFS 알고리즘 예제
예제) 백준 2606. 바이러스
💡 문제 확인
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 위의 그림과 같이 네트워크 상에서 연결되어 있다고 하자.
1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.
하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
💡 바이러스 문제의 해법
1번 노드에서 도달할 수 있는 다른 노드의 개수를 출력하는 문제로 DFS를 이용해 양방향 그래프에 대한 그래프 탐색을 진행할 수 있다.
💡 바이러스 문제 해결 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let n = 7; // 정점의 개수(N)
let m = 6; // 간선의 개수(M)
let graph = [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]; // 그래프 정보 입력
let cnt = 0;
let visited = new Array(n + 1).fill(false);
function dfs(x) {
// 깊이 우선 탐색(DFS) 수행
visited[x] = true; // 현재 노드를 방문 처리
cnt++;
for (y of graph[x]) {
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
if (!visited[y]) dfs(y);
}
}
dfs(1);
console.log(cnt - 1); // 4
📑 참고 자료
[Algorithm/Java] DFS(깊이 우선 탐색)