[TIL, 일일 회고] 2024.12.12 - Backtracking 알고리즘에서 visited 배열을 사용해야 할까❓

 

 

개요

백트래킹(Backtracking) 알고리즘을 구현할 때 가장 흔히 사용되는 방법 중 하나가 boolean[] visited 배열입니다.
 

[Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기

하지만 모든 백트래킹 문제에 visited 배열이 필요한 것은 아닙니다. 이번 포스트에서는 visited 배열을 사용해야 하는 경우와 그렇지 않은 경우를 정리하고자 합니다.

 

visited 배열이 필요한 경우

visited 배열은 주로 중복 선택을 방지해야 할 때 사용됩니다. 대표적인 예시로는 순열(Permutation)을 구하는 문제가 있습니다.

• 백준 - N 과 M (1)

[백준, 15649번] N과 M(1) (백트래킹, Java)

visited 배열이 각 숫자의 사용 여부를 체크하여 중복 선택을 방지합니다.

 

vivisited 배열이 필요없는 경우

visited 배열(중복 체크) 없이도 백트래킹을 구현할 수 있는 경우들이 있습니다.

1. 중복 선택이 가능한 경우

public class DuplicateSelection {
    static int N = 4;  // 전체 숫자의 개수
    static int M = 2;  // 선택할 숫자의 개수
    static int[] result = new int[M];
    
    public static void main(String[] args) {
        backtrack(0);
    }
    
    static void backtrack(int depth) {
        if (depth == M) {
            printArray(result);
            return;
        }
        
        for (int i = 0; i < N; i++) {
            result[depth] = i + 1;
            backtrack(depth + 1);
        }
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

2. 오름차순 조합

public class AscendingCombination {
    static int N = 4;  // 전체 숫자의 개수
    static int M = 2;  // 선택할 숫자의 개수
    static int[] result = new int[M];
    
    public static void main(String[] args) {
        backtrack(0, 1);  // 1부터 시작
    }
    
    static void backtrack(int depth, int start) {
        if (depth == M) {
            printArray(result);
            return;
        }
        
        for (int i = start; i <= N; i++) {
            result[depth] = i;
            backtrack(depth + 1, i + 1);  // 다음 숫자부터 시작
        }
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3. 선택/미선택 백트래킹

public class SelectOrNot {
    static int N = 4;  // 전체 숫자의 개수
    static boolean[] selected = new int[N];
    
    public static void main(String[] args) {
        backtrack(0);
    }
    
    static void backtrack(int depth) {
        if (depth == N) {
            printSelected();
            return;
        }
        
        // 현재 원소를 선택하는 경우
        selected[depth] = true;
        backtrack(depth + 1);
        
        // 현재 원소를 선택하지 않는 경우
        selected[depth] = false;
        backtrack(depth + 1);
    }
    
    static void printSelected() {
        for (int i = 0; i < N; i++) {
            if (selected[i]) {
                System.out.print((i + 1) + " ");
            }
        }
        System.out.println();
    }
}

 

 

visited 사용 여부를 결정하는 기준

• visited 배열이 필요한 경우
  • 순열(Permutation)처럼 중복 선택을 방지해야 할 때
  • 그래프 탐색에서 같은 노드를 재방문하지 않아야 할 때
  • 특정 요소의 사용 여부를 추적해야 할 때
• visited 배열이 필요없는 경우
  • 중복 선택이 허용되는 경우
  • 오름차순/내림차순으로 선택하는 경우 (start 변수로 제어)
  • 단순히 선택/미선택의 두 가지 경우만 다루는 경우
  • 범위나 인덱스로 중복을 제어할 수 있는 경우

결국 "이 원소를 이미 사용했는지 체크"가 필요한 상황이라면 boolean 배열을 사용하고, 그렇지 않다면 생략할 수 있습니다.