그래프 탐색 알고리즘 - 깊이 우선 탐색 [DFS]

깊이 우선 탐색(DFS, Depth-First Search)

DFS는 그래프 탐색 알고리즘 중 하나로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하여 차례대로 탐색하는 알고리즘이다.

 

DFS는 주로 스택(Stack)을 통해 구현하거나, 재귀문을 통하여 구현한다.

---

DFS 작동 원리

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.

4. 2 ~ 3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

 

DFS의 작동원리를 이해하기 위해 아래 사진을 준비했다.

아래 예제에서는 번호가 낮은 순서부터 처리하도록 구현하는 방법을 사용했다.
(코딩 테스트에서는 명시적으로 낮은 순서부터 처리하도록 문제를 제시하는 경우가 보편적이다.)

 

 

Step1 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 한다.

 

step2 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8'번 중 가장 작은 노드인 '2'를 스택에 넣고 방문 처리를 한다.

 

Step3 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'번 노드를 스택에 넣고 방문 처리를 한다.

 

Step4 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6', '8'번 중 가장 작은 노드인 '6'번 노드를 스택에 넣고 방문 처리를 한다.

 

Step5 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '6'번 노드를 꺼낸다.

 

Step6 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'번 노드를 스택에 넣고 방문 처리를 한다.

 

Step7 스택의 최상단 노드인 '8'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '8'번 노드를 꺼낸다.

 

Step8 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '7'번 노드를 꺼낸다.

 

Step9 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '2'번 노드를 꺼낸다.

 

Step10 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '3'번을 스택에 넣고 방문 처리를 한다.

 

Step11 스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '4', '5'번 중 가장 작은 노드인 '4'번 노드를 스택에 넣고 방문 처리를 한다.

 

Step12 스택의 최상단 노드인 '4'에 방문하지 않은 인접 노드 '5'번을 스택에 넣고 방문 처리를 한다.

 

Step13 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.

 

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

---

DFS 알고리즘 구현 - 자바

DFS 깊이 우선 탐색의 핵심은 '가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없다면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다' 이다.

 

 

재귀문 사용

void DFS(int idx) {
    // 시작 정점 방문 처리
    visit(idx);
    
    // 정점과 인접한 노드들을 확인한다.
    for (Node node : linkedNode(idx)) {
        // 아직 방문하지 않은 노드인 경우, 재귀적으로 탐색한다.
        if (!isVisit(node)) {
            DFS(node.getIdx);
        }
    }
}

재귀문을 통해 DFS 알고리즘을 구현하면 코드가 직관적이고 구현하기 쉽다는 장점이 있다.

하지만 재귀함수를 이용하기 때문에, 함수 호출 비용이 추가로 들어가고, 재귀의 깊이가 지나치게 깊어진다면 메모리 비용을 예측하기 어렵다는 단점이 있다.

 

 

스택 자료구조 사용

void DFS(int idx) {
        // 시작 정점을 스택에 추가
        Stack<Integer> stack = new Stack<>();
        stack.push(idx);

        while (!stack.isEmpty()) {
            int current = stack.pop();

            // 현재 정점이 이미 방문된 경우 건너뛴다.
            if (isVisit(current)) {
                continue;
            }

            // 현재 정점 방문 처리
            visit(current);

            // 현재 정점과 인접한 노드들을 스택에 추가 (미방문 노드만)
            for (Node node : linkedNode(current)) {
                if (!isVisit(node)) {
                    stack.push(node.getIdx());
                }
            }
        }
    }

선입후출의 특성을 가진 스택(Stack) 자료구조를 사용하여 가장 최근에 방문한 노드를 확인할 수 있다.

스택 자료구조를 사용하면 시스템 스택을 사용하는 재귀문과 달리, 메모리 사용량이 비교적 예측 가능하며, 시스템 스택 한계를 넘기지 않으므로 더 안정적이라는 장점이 있다. 하지만 재귀문에 비해 코드의 가독성이 낮고, 구현이 복잡하여 이해가 어렵다는 단점이 있다.

 

 

 

재귀문을 사용하면 직접 스택 자료구조를 구현하지 않아도 운영체제의 시스템 스택을 사용할 수 있다는 간편함에 일반적으로 DFS 를 구현할 때 재귀함수를 이용하여 구현하시는 사람이 많은 것 같다. 하지만 스택을 직접 사용하는 것이 크게 어려운 것이 아니니 취향에 따라 선택해서 구현하면 될 것 같다.

---

연습문제 추천

• 백준 - 1260, 2606, 2667
• 프로그래머스 - 네트워크

출처
- [10분 테코톡] 📚카프카의 탐색 알고리즘
- 이것이 취업을 위한 코딩 테스트다 with 파이썬
- 코딩 테스트 합격자 되기 - 자바 편