[알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

참고 포스트

 

https://rnasterofmysea.tistory.com/76

 

- 이전 포스트 내용 중 

백트래킹은 모든 경우의 수를 탐색한다 + 그래프(트리)간의 level 이동이 가능하다 라는 특징이 있습니다.
 
* 모든 경우의 수를 탐색한다 == 조합을 생성한다.

* 그래프(트리) 간의 level 이동이 가능하다 == 연속성, 방향성 등에 관한 configuration을 관리한다.

 

백트래킹이란?

백트래킹은 가능한 모든 경우의 수를 탐색하는 알고리즘으로, 주어진 조건에 맞는 해를 찾는 데 적합합니다. DFS(깊이 우선 탐색)를 기반으로 작동하며, 탐색 도중 조건에 맞지 않는 경우 가지치기(Pruning)를 통해 불필요한 경로를 제거합니다.

 

2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

[자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

 

---

DFS와 백트래킹의 차이점

DFS는 단순히 그래프나 트리의 모든 노드를 방문하기 위한 탐색 기법입니다. 반면, 백트래킹은 문제의 제약 조건에 맞는 경로만 탐색하며, 다음과 같은 차별점이 있습니다:

1. DFS는 모든 노드를 방문하는 것을 목표로 하지만, 백트래킹은 조건을 만족하는 경우만 탐색합니다.
2. 백트래킹은 탐색 중 노드 간 상하 이동을 통해 경로를 되돌아가며 다른 선택지를 시도합니다.
3. DFS 탐색의 확장으로, 중복 방지, 방향성 설정, 조건 추가 등을 설계에 포함할 수 있습니다.

---

백트래킹에서 DFS를 사용하는 이유

1. 깊게 탐색 가능: 문제의 요구사항에 맞는 노드 레벨까지 깊이 탐색할 수 있습니다.
2. 효율적인 경로 탐색: 탐색 도중 조건에 맞지 않으면 상하 이동(Backtrack)을 통해 경로를 변경하며, 모든 경우의 수를 효과적으로 탐색합니다.
3. 유연한 설계: 방문 여부, 방향성, 중복 방지 등 다양한 조건을 재귀 구조에 통합하여 문제에 맞게 설계할 수 있습니다.

---

백트래킹 설계의 핵심: 경우의 수(조합) + 노드 간 상하 이동

백트래킹에서의 노드 간 상하 이동은 특정 조건에 따라 경로를 선택적으로 탐색하고, 조건에 맞지 않으면 이전 단계로 되돌아가는 동작을 의미합니다. 이를 통해 모든 경우의 수를 탐색하거나, 원하는 값만 선택적으로 탐색할 수 있습니다.

 

노드 간의 상하 이동 설계 방법

 

기본 설계: visited 배열 활용

• 방문 여부를 기록하여 중복 탐색을 방지.
• 예: N과 M 문제에서 visited를 사용하여 선택된 숫자를 제외하고 다음 숫자를 탐색.

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

 

void backtrack(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = 1;  // 방문 체크
            result[depth] = i;
            backtrack(depth + 1);
            visited[i] = 0;  // 방문 해제
        }
    }
}

---

visited 배열 없이 구현한 백트래킹

• 해당 문제는 visited 배열 없이 연산자의 갯수를 감소시켰다가 백트래킹시 다시 증감시키면서 백트래킹을 구현합니다. 즉, 노드 계층(level)간의 이동(백트래킹)을 연산자의 갯수를 통해 조절합니다.

https://rnasterofmysea.tistory.com/75

C - [백준 14888] 연산자 끼워넣기 (feat. 백트래킹 + DFS)

 

void dfs(int depth, int result) {
    if (depth == N) {
        // 모든 연산을 끝낸 경우 결과 갱신
        if (result > MAX) MAX = result;
        if (result < MIN) MIN = result;
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (operators[i] > 0) {
            operators[i]--; // 연산자 사용
            int next_result = result;

            // 연산 수행
            if (i == 0) next_result += numbers[depth];          // 덧셈
            else if (i == 1) next_result -= numbers[depth];     // 뺄셈
            else if (i == 2) next_result *= numbers[depth];     // 곱셈
            else if (i == 3) {                                  // 나눗셈
                if (next_result < 0) 
                    next_result = -(-next_result / numbers[depth]);
                else 
                    next_result /= numbers[depth];
            }

            dfs(depth + 1, next_result); // 다음 단계로 이동
            operators[i]++; // 연산자 복구
        }
    }
}

 

---

방향성을 추가한 설계

• 탐색 방향을 제한하여 특정 조건을 만족하는 경로만 탐색.
• 예: BFS 문제였던 미로 탐색(https://rnasterofmysea.tistory.com/51)에서 상하좌우(x,y) 경로 탐색을 응용하여  N-Queen 문제에서 대각선 조건을 추가.

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 9663] N-Queen (feat. 백트래킹, DFS)

C - [백준 9663] N-Queen (feat. 백트래킹, DFS)

 

void nQueen(int row) {
    if (row == N) {
        count++;
        return;
    }
    for (int col = 0; col < N; col++) {
        if (!cols[col] && !diag1[row + col] && !diag2[row - col + N - 1]) {
            cols[col] = diag1[row + col] = diag2[row - col + N - 1] = 1;
            nQueen(row + 1);
            cols[col] = diag1[row + col] = diag2[row - col + N - 1] = 0;
        }
    }
}

 

---

중복값 방지 조건 추가 (중복 없는 조합)

• 탐색 과정에서 중복된 값을 제외하여 유효한 조합만 탐색.
• 로또 문제에서 조합의 시작점을 i+1로 설정하여 중복을 없앴는데 이를 위해 두가지 변화가 생겼습니다.
  1.  DFS 함수 (이 문제에서 combination 함수) 의 매개변수로 조합의 시작점이 필요합니다.
     1. void combination(int depth, int start) 
     2. 재귀 호출 시, combination(depth +1, i + 1)
  2.  반복문의 시작 지점의 변화
     1. for(int i = start ; i < N; i++)
• 중복 값이 허용되었을 때는 조합의 시작점이 필요 없었으며 for문에서도 0부터 시작했습니다.

 

2025.01.07 - [Computer Science/알고리즘 문제] - C - [백준 6603] 로또 (feat. 백트래킹)

 

void combination(int depth, int start) {
    if (depth == 6) {
        for (int i = 0; i < 6; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }
    for (int i = start; i < N; i++) {
        result[depth] = array[i];
        combination(depth + 1, i + 1);  // 시작점을 i+1로 설정하여 중복 방지
    }
}

 

---

결론

백트래킹은 단순히 "모든 경우의 수를 탐색"하는 알고리즘이 아닙니다. 문제의 제약 조건에 맞춘 노드 간 이동 설계를 통해 원하는 값을 효율적으로 구할 수 있습니다.

 

1. 노드 간의 이동을 visited 배열을 통해 구현할 수 있으나, 문제의 조건에 따라 visited 배열이 필요할 수도, 필요없을 수도 있습니다. ()

 

2. DFS 탐색의 반복 범위를 조절함으로써 중복값을 허용할 수도, 불허할수도 있습니다. (로또 문제)

 

3. 탐색 조건을 추가하여 문제의 요구사항을 충족할 수 있습니다. (N-queen 문제)

 

 

DFS의 탐색 구조를 기반으로 하되, 조건을 만족하지 않는 경로는 가지치기하며, 중복 방지, 방향성 설정, 특정 조건 추가 등 문제 요구사항에 따라 유연하게 설계할 수 있습니다.

이를 이해하고 응용하면 복잡한 알고리즘 문제도 효과적으로 해결할 수 있습니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.