취미겸생업

[Algorithm] DFS, 백트래킹 본문

IT/Algorithm

[Algorithm] DFS, 백트래킹

nohumb 2026. 7. 13. 15:32
SMALL

DFS

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

그래프 순회 순서

루트 노드에서 시작해, 다음 분기(Branch)로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법이다. 노드 순회 시, 깊이를 우선으로 모든 노드를 방문하고자 할 경우 사용한다. 단순 검색 속도 자체는 BFS에 비해 느리다.

특성

  • 전위 순회(Pre-Order) 방법 또한 DFS의 일종
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함 (검사하지 않을 경우 무한루프 발생)
  • 깊이 우선 순위로 모든 노드에 대한 완전 탐색

DFS 과정

요소의 역할

  • Stack : 현재 탐색 상태(탐색한 경로와 되돌아갈 경로)를 기억하기 위한 자료구조
  • Visited : 한 번 방문한 노드를 다시 방문하지 않기 위한, 모든 노드에 대한 방문 여부 체크리스트

준비 단계

  • Visited를 모두 false로 초기화하여 모든 노드에 대한 방문 여부 초기화

탐색 과정

  1. 루트 노드에서 탐색 시작, Stack에 루트 노드를 Push
  2. 아래 과정을 반복하고, Stack이 비어있다면 DFS 과정 종료
    1. Stack에서 노드를 Pop하여 현재 노드로 설정
    2. 현재 노드가 visited == true라면 a. 단계로 되돌아가 다음 노드를 Pop
    3. 현재 노드가 visited == false라면, visited = true로 설정하고 필요한 로직을 수행
    4. visited == false인 모든 이웃 노드를 Stack에 Push

재귀를 이용한 DFS 예시

  • 예시 코드

    • 기본형

      • 노드 구조

          /* 노드 구조

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

  */

      • 코드

          import java.util.*;

  public class RecursiveDfsExample {
      private static Set<Node> visited = new HashSet<>();

      public static void main(String[] args) {
          Node n_4 = new Node(4);
          Node n_5 = new Node(5);
          Node n_6 = new Node(6);
          Node n_7 = new Node(7);
          Node n_2 = new Node(2, n_4, n_5);
          Node n_3 = new Node(3, n_6, n_7);
          Node n_1 = new Node(1, n_2, n_3);

          dfs(n_1);
      }

      public static void dfs(Node current) {
          if(current == null) {
              return; // 루트 노드로 되돌아오거나 끝 노드일 경우 추가 탐색 종료
          }

          if(visited.contains(current)) {
              return; // 이미 방문한 노드일 경우 pop
          } else {
              visited.add(current);
              System.out.print(current.data + " ");
          }

          if(!visited.contains(current.left)) {
              dfs(current.left); // 다음 노드 Stack push
          }

          if(!visited.contains(current.right)) {
              dfs(current.right);
          }
      }

      public static class Node {
          private int data;
          Node left;
          Node right;

          public Node(int data, Node left, Node right) {
              this.data = data;
              this.left = left;
              this.right = right;
          }

          public Node(int data) {
              this.data = data;
          }
      }
  }

스택을 이용한 DFS 예시

  • 스택을 활용한 명시적 DFS는 visited 자료구조를 제어하는 타이밍이나 탐색 순서를 Stack을 통해 직접 제어해야 하기 때문에 재귀보다 훨씬 복잡하다.

  • 예시 코드

    • 기본형

      • 노드 구조

          /* 노드 구조

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

  */

      • 코드

          import java.util.*;

  public class StackDfsExample {
      public static void main(String[] args) {
          Stack<Node> stack = new Stack<>();
          Set<Node> visited = new HashSet<>();

          Node n_4 = new Node(4);
          Node n_5 = new Node(5);
          Node n_6 = new Node(6);
          Node n_7 = new Node(7);
          Node n_2 = new Node(2, n_4, n_5);
          Node n_3 = new Node(3, n_6, n_7);
          Node n_1 = new Node(1, n_2, n_3);

          stack.push(n_1); // 1.

          while(!stack.isEmpty()) { // 2.
              Node current = stack.pop(); // 2-a.

              if(visited.contains(current)) { // 2-b.
                  continue;
              } else {  // 2-c.
                  visited.add(current);

                  System.out.print(current.data + " ");
              }

              // 2-d.
              if(current.right != null && !visited.contains(current.right)) {
                  stack.push(current.right);
              }

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

      public static class Node {
          private int data;
          Node left;
          Node right;

          public Node(int data, Node left, Node right) {
              this.data = data;
              this.left = left;
              this.right = right;
          }

          public Node(int data) {
              this.data = data;
          }
      }
  }

백트래킹

백트래킹

DFS 또는 BFS 알고리즘 등 탐색 알고리즘 중 왔던 길을 되돌아가는 기법을 사용하는 것을 말한다.

순수 DFS는 단순히 모든 노드를 탐색하기만 한다면, 백트래킹은 기존에 방문한 노드의 방문 상태를 해제하여 재방문하는 등, 탐색 순서와 조합을 유연하게 제어하는 접근이 가능하다.

예제 코드

  • 1~N 중 k개 뽑아 합 출력하기 (Combination-조합, 순서 상관 없음)

    • 아이디어

        /*
  <N개의 카드 중 k개 뽑아 합 출력하기>
  1, 2, 3, 4에 대해 3개
  - 1 + 2 + 3 = 6
  - 1 + 2 + 4 = 7
  - 1 + 3 + 4 = 8
  - 2 + 3 + 4 = 9
  */

    • 코드

      • for 문의 초기값 설정을 통해 다음 노드 방향에 대한 가지치기

      • 탐색하지 않아도 될 노드는 탐색하지 않음

        public class DfsCombination {
  static int n, k;
  static int[] selected;

  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      k = sc.nextInt();
      selected = new int[k];

      combination(0, 1);
  }

  static void combination(int start, int depth) {
  if (depth == k) {
      int sum = 0;
      for(int num : selected){
          sum += num;
      }
      System.out.println(sum);
          return;
  }

  for (int i = start; i <= n; i++) {
        selected[depth] = i;
      combination(i + 1, depth + 1);
  }
  }
}

  • 1~N 중 k 자릿수 만들어 출력하기 (Permutation-순열, 순서 상관 있음)

    • 아이디어

        /*
  <1~N개의 카드 중 k개 뽑아 숫자 만들기 (순열)>
  1, 2, 3, 4에 대해 3개 뽑기

      1             2
     /|  \         /|  \
    2 3   4       1 3   4 
   /| |\  |\     /| |\  |\ 
  3 4 2 4 2 3   3 4 1 4 1 3   ...

  - 123, 124, 132, 134, 142, 143
  - 213, 214, 231, 234, 241, 243
  - 312, 314, 321, 324, 341, 342
  - 412, 413, 421, 423, 431, 432
  */

    • 코드

        public class DfsPermutation {
      static int n;
      static int k;
      static int[] selected;
      static boolean[] visited;

      public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
          n = sc.nextInt();
          k = sc.nextInt();
          visited = new boolean[n+1];
          selected = new int[k];

          permutation(0);
      }

      static void permutation(int depth) {
      if (depth == k) {
          System.out.println(Arrays.toString(selected));
              return;
      }

      for (int i = 1; i <= n; i++) {
          if (!visited[i]) {
              visited[i] = true;
              selected[depth] = i;

              permutation(depth + 1);

              visited[i] = false;
          }
      }
      }
  }

  • N개 중 k 자릿수 만들어 출력하기 (Permutation 응용)

      public class DfsPractice {
      static int k;
      static int[] nums;
      static int[] selected;
      static boolean[] visited;

      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          k = sc.nextInt();
          nums = new int[]{1, 3, 5, 7, 9};
          selected = new int[k];
          visited = new boolean[nums.length];

          dfs(0);
      }

      static void dfs(int depth) {
          if(depth == k) {
              for(int index : selected) {
                  System.out.print(nums[index] + " ");
              }
              System.out.println("");
              return;
          }

          for(int i=0; i < nums.length; i++) {
              if(!visited[i]) {
                  visited[i] = true;
                  selected[depth] = i;

                  dfs(depth + 1);

                  visited[i] = false;
              }
          }
      }
  }
LIST
저작자표시 비영리 동일조건 (새창열림)