[묘공단] 깊이 우선 탐색(DFS)

코테를 풀다 보면 깊이우선탐색, 너비우선탐색을 자주 볼 수 있다.

해당 알고리즘은 무엇일까?

 

DFS, BFS는 트리를 순회하는 방법이다.

 

1. 트리라고 하면 아래와 같은 그림을 바로 떠올릴 수 있다. 그럼 아래와 같은 구조를 바탕으로 풀어야 하는 문제 유형은 무엇이 있을까?

https://www.geeksforgeeks.org/tree-data-structure/

트리 문제는 주로 트리 순회, 이진 탐색 트리(BTS) 연산, 균형 트리, 특수 트리, 그리고 트리의 경로와 거리 계산으로 나뉜다.

모든 걸 다 보면 좋을 것이고, 앞으로 다 살펴볼 것이지만 이번 시간에는 트리 순회 문제에 대해서만 다룬다.

트리 순회 문제는 DFS, BFS를 이용해 특정 노드를 찾거나 순서를 출력하는 식이다.

기억하자. 트리를 순회해야 된다? -> DFS나 BFS로 푼다.

 

* 참고 *

이진 탐색 트리 연산 문제는 삽입, 삭제, 검색을 통해 푼다.

균형 트리 문제는 AVL 트리나 레드-블랙 트리를 통해 균형을 유지하는 방법으로 푼다.

특수 트리 문제는 힙, 트라이, 세그먼트 트리와 같은 특수한 용도의 트리로 푼다.

트리의 경로와 거리 계산 문제는 트리의 지름, 최소/최대 깊이, 특정 경로 합 등을 계산해서 푼다.

---

여기까지 리서치 하다 보니 궁금해졌다.

2. 트리라는 자료구조에서 이런 문제 유형? 풀이법?이 나오는 이유가 뭘까?

이는 트리가 많은 실제 문제를 모델링할 수 있는 강력한 자료구조이기 때문이라고 한다.

실제로 트리는 계층 구조를 표현하는 데 적합해 파일 시스템, 조직도, 컴파일러의 구문 분석 등 다양한 분야에서 사용되고 있다.

 

트리 순회 방법은 트리의 각 노드를 체계적으로 방문하기 위해 필요한데 이를 통해 데이터를 특정 순서로 처리할 수 있다.

이진 탐색 트리는 정렬된 데이터를 효율적으로 저장하고 검색할 수 있어 데이터베이스와 같은 응용 분야에서 유용하다.

균형 트리는 삽입과 삭제 연산 후에도 트리의 높이를 일정하게 유지해 검색 속도를 빠르게 한다.

힙이나 트라이 같은 특수 트리는 특정한 작업(최소값/최대값 찾기, 문자열 검색 등)을 효율적으로 수행하도록 설계됐다.

트리의 경로와 거리 계산 문제는 네트워크 지연 시간 계산, 데이터 전송 경로 최적화 등 실세계 문제를 해결하는 데 도움이 된다.

 

3. 트리는 DFS, BFS로만 순회해야 하나?

그렇지 않다.

알다시피 전위 순회, 중위 순회, 후위 순회 등이 있다.

각 순회 방식은 다른 정보를 제공한다.

전위 순회는 노드를 복사하는 데 사용한다.

중위 순회는 정렬된 순서를 얻는 데 적합하다.

후위 순회는 노드를 삭제하는 데 유리하다.

레벨 순회는 트리 구조를 시각화하는 데 도움이 된다.

 

DFS, BFS를 사용하는 이유는

1. 다양한 문제를 해결하기 좋다

전위, 중위, 후위 순회는 특정 패턴의 순회 방법이지만, DFS와 BFS는 더 일반적인 탐색 방법이다.

따라서 다양한 유형의 문제를 해결하는 데 이게 더 쓰기 좋다.

2. 특정 문제에 응용하기 좋다

BFS는 최단 경로 문제에 쓰기 좋다.

네트워크 경로 최적화나 트리의 최소 깊이를 찾아야 한다면 BFS다.

DFS는 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾는 데 쓰인다.

3. 트리 구조를 이해하기 좋다

BFS는 트리의 레벨별 구조를 이해하고 시각화하는 데 도움이 된다.

트리의 구조적 특성을 파악해야 하거나 레벨별 처리가 필요한 문제에서는 BFS를 쓴다.

4. 공통 조상을 찾아야 할 때 쓴다

DFS는 공통 조상(LCA) 찾기 문제에서 효율적으로 사용된다.

5. 메모리를 효율적으로 사용해야 할 때 쓴다

DFS를 쓰면 재귀 호출을 사용하거나 스택을 이용해 메모리 사용을 최적화할 수 있다.

BFS를 사용하면 큐를 써서 메모리를 일정하게 사용할 수 있다.

---

서론이 길었다.

 

그래서

4. DFS란 무엇인가?

DFS는 Depth-First Search를 뜻한다.

깊이 우선 탐색.

말만 들어도 아래와 같을 것 같지 않은가?

https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/

미리 말해 두자면 DFS는 트리에서도 그래프에서도 가능하다.

* 참고 *

그래프가 트리보다 상위 개념이다.

그래프가 트리를 포함하며 더 일반적인 개념이라는 말이다.

그래프는 노드와 엣지로 구성된 자료구조인데 사이클은 있을 수도 있고 없을 수도 있다.

https://mathinsight.org/network_introduction

사이클이란? => 그래프 내에서 같은 노드를 두 번 이상 방문하게 되는 경로.

 

트리는 그래프의 한 종류로, 사이클 없이 연결된 구조다.

하나의 루트 노드와 자식 노드들로 구성된다.

 

트리에서의 DFS와 그래프에서의 DFS 차이를 이야기하자면 시간이 많이 걸릴 것 같아

아래에 별도 설명을 첨부한다.

트리에서의 DFS

• 트리는 사이클이 없는 연결된 그래프의 일종입니다.
• 트리에서는 루트에서 시작하여 모든 자식 노드를 깊이 우선으로 탐색합니다.
• 트리에는 루프가 없기 때문에 방문한 노드를 추적할 필요가 없습니다.

그래프에서의 DFS

• 그래프는 노드와 엣지가 있는 일반적인 자료구조로, 사이클이 있을 수 있습니다.
• 그래프에서는 임의의 노드에서 시작하여 깊이 우선으로 탐색합니다.
• 그래프에는 사이클이 있을 수 있기 때문에, 방문한 노드를 추적해야 합니다.

공통점과 차이점

• 공통점: DFS는 트리와 그래프 모두에서 사용 가능한 알고리즘입니다.
• 차이점: 그래프의 DFS에서는 사이클을 피하기 위해 방문 여부를 체크해야 합니다.

결론적으로, DFS는 트리 순회 방법 중 하나이지만, 그래프 탐색에도 널리 사용됩니다. 트리와 그래프 모두에서 DFS를 사용할 수 있으나, 그래프에서는 추가로 방문 체크가 필요합니다.

여튼 다시 DFS로 돌아와서,

이는 트리나 그래프에서(이 글에서는 트리만 이야기하겠다.) 한 경로를 가능한 깊이까지 탐색한 후, 다른 경로를 탐색하는 방법이다. <- 이 페이지에서 가장 중요한 핵심 포인트.

 

DFS는 다음과 같은 경우에 쓴다.

위에서는 특정 노드를 찾거나 순서를 출력하는 데 쓴다고 말했지만 여기에서는 더 자세히 이야기하겠다.

1. 모든 노드를 방문해야 할 때 

2. 먼저 한 경로를 끝까지 탐색하고, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색해야 할 때(백트래킹 포함)

3. 경로 찾기, 사이클 검출, 강한 연결 요소, 위상 정렬 등의 문제

4. 재귀 호출을 사용하거나 스택을 써야 할 때(사용하는 게 좋을 때)

 

5. DFS를 사용하는 방법은?

1. 시작 노드를 스택에 넣는다.

2. 스택에서 노드를 꺼내 처리한다.

3. 해당 노드의 자식 노드를 스택에 넣는데 오른쪽 자식을 먼저 넣고 왼쪽 자식을 나중에 넣는다.

4. 스택이 빌 때까지 2~3단계를 반복한다.

---

그 전에 재귀를 사용한 (가장 기본적인 형식의) 코드로 이해해 보자.

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class DFSTree {
    // DFS 함수
    public void dfs(Node node) {
        if (node == null) {
            return;
        }

        // 현재 노드를 방문
        System.out.print(node.value + " ");

        // 왼쪽 자식 노드로 이동
        dfs(node.left);

        // 오른쪽 자식 노드로 이동
        dfs(node.right);
    }

    public static void main(String[] args) {
        // 간단한 트리 생성
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        // DFS 실행
        DFSTree tree = new DFSTree();
        tree.dfs(root);  // 출력: 1 2 4 5 3
    }
}

    1
   / \
  2   3
 / \
4   5

이제 스택을 사용한 방법을 보자.

스택을 사용한 방법은 그냥 재귀를 스택으로 대체한 것 뿐이다.

import java.util.Stack;

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class DFSTree {
    // 스택을 이용한 DFS 함수
    public static void dfs(Node root) {
        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            System.out.print(current.value + " ");

            // 스택의 특성상 먼저 오른쪽 자식을 넣어야 나중에 방문함
            if (current.right != null) {
                stack.push(current.right);
            }

            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }

    public static void main(String[] args) {
        // 간단한 트리 생성
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        // DFS 실행
        DFSTree.dfs(root);  // 출력: 1 2 4 5 3
    }
}

 

그럼 이제 문제를 하나 풀어 보자.

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

이 문제를 DFS로 풀 수 있다는 힌트는 어디에서 얻을 수 있을까?

1. '더하거나 빼서' <- 선택지가 두 가지

2. 모든 가능한 조합을 탐색해야 한다는 점

 

                                                  dfs(0, 0)
                                        /                        \
                             dfs(1, 1)                            dfs(1, -1)
                           /               \                    /                \
                   dfs(2, 2)            dfs(2, 0)          dfs(2, 0)            dfs(2, -2)
                  /         \            /        \         /        \            /         \
          dfs(3, 3)   dfs(3, 1)   dfs(3, 1)   dfs(3, -1)   dfs(3, 1)   dfs(3, -1)   dfs(3, -1)   dfs(3, -3)
         /      \     /      \     /      \     /      \     /      \     /      \     /      \     /      \
dfs(4, 4) dfs(4, 2) dfs(4, 2) dfs(4, 0) dfs(4, 2) dfs(4, 0) dfs(4, 2) dfs(4, 0) dfs(4, 2) dfs(4, 0) dfs(4, 0) dfs(4, -2) dfs(4, 0) dfs(4, -2) dfs(4, -2) dfs(4, -4)
 /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \    /   \
dfs(5, 5) dfs(5, 3) dfs(5, 3) dfs(5, 1) dfs(5, 3) dfs(5, 1) dfs(5, 3) dfs(5, 1) dfs(5, 3) dfs(5, 1) dfs(5, 1) dfs(5, -1) dfs(5, 1) dfs(5, -1) dfs(5, -1) dfs(5, -3)

 

인덱스가 5에 최종 값이 3이 되는 건 5가지 경우만 나온다.

public class Solution {
    public static int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private static int dfs(int[] numbers, int target, int index, int currentSum) {
        // 모든 숫자를 다 사용한 경우
        if (index == numbers.length) {
            // 현재 합이 타겟 넘버와 같은지 확인
            if (currentSum == target) {
                return 1;
            } else {
                return 0;
            }
        }

        // 현재 숫자를 더하는 경우
        int countWithAddition = dfs(numbers, target, index + 1, currentSum + numbers[index]);
        // 현재 숫자를 빼는 경우
        int countWithSubtraction = dfs(numbers, target, index + 1, currentSum - numbers[index]);

        // 두 경우의 합을 반환
        return countWithAddition + countWithSubtraction;
    }
}

 

골든래빗 출판사의 묘공단 스터디를 진행하며

코딩 테스트 합격자 되기 - 자바 편 프로그래머스 제공 97 문제로 완벽 대비를 읽고 정리한 내용입니다.