# 백트래킹(Backtracking)

## 백트랙킹이란?

- 백트래킹(Backtracking) 알고리즘은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(Backtrack)해 정답을 찾아가는 알고리즘
- 이 알고리즘은 모든 가능한 상태를 탐색하는 브루트 포스 방식의 탐색을 기반으로 하지만, 불필요한 탐색 경로를 조기에 포기함으로써 시간을 절약한다.
- 이러한 방식은 트리 구조를 이용해 상태 공간을 탐색하는데, 이때 각 분기점(branch)에서 검사를 수행하여 불필요한 탐색을 줄인다.
- 백트래킹 알고리즘은 주로 최적화 문제와 결정 문제에서 사용된다
- 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 '예' 혹은 '아니오'로 답하는 문제를 의미
> **예시: 미로찾기**
>
> - 미로에서 빠져나갈 경로가 존재하는가? -> 결정 문제
> - 미로에서 최단거리로 나갈 수 있는 경로는 무엇인가? -> 최적화 문제
- 장점
- 문제의 해를 찾기 위해 필요한 시간을 크게 줄일 수 있다.
- 특히 특정 조건을 만족하지 않는 해를 빠르게 배제하고 다른 가능한 해를 탐색하기 때문
- 백트래킹은 다양한 문제에 적용할 수 있다.
- 가능한 모든 해를 탐색하므로 문제의 모든 해를 찾아내는데 효과적이다.
- 단점
- 일반적으로 NP-완전 문제에 대해 사용되며, 이러한 문제의 경우 최악의 시나리오에서 시간 복잡도는 지수적으로 증가할 수 있다.
- 재귀 호출을 사용하기 때문에 스택 메모리 사용량이 늘어날 수 있다.
- 해가 없는 경우에 비효율적일 수 있다.
- 이는 모든 가능한 경로를 탐색해야 하기 때문에 시간이 많이 소요될 수 있다.

## 백트랙킹과 재귀호출


### **재귀(Recursion)**

- **일반적인 프로그래밍 기법**
- 함수가 자신을 다시 호출하는 것을 의미
- 복잡한 문제를 작은 부분 문제로 나누는 방식을 구현하는 데 사용된다.
- 프로그램의 구조를 단순화하고, 코드를 간결하게 만들 수 있지만, 메모리 사용에 주의해야 한다.

### **백트래킹(Backtracking)**

- **특정한 문제를 해결하기 위한 알고리즘 전략**
- 문제의 해결책을 찾기 위해 사용되는 알고리즘 설계 전략이다.
- 가능한 모든 해결책을 탐색하되, 어떤 선택지가 더 이상 유망하지 않다고 판단되면 (즉, 해결책으로 이어질 수 없다면) 이전 상태로 되돌아간다.
- 이는 결정 트리에서 종종 볼 수 있는 전략이며, 백트래킹 알고리즘은 일반적으로 재귀적으로 구현된다.

## 백트랙킹 알고리즘 예시

1. DFS & BFS 문제
- BFS와 DFS를 이용하여 그래프를 탐색하는 문제
- 백준 알고리즘 1260번 ==[링크](https://www.acmicpc.net/problem/1260)==
2. N과 M (1) 문제
- 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제
- 백준 알고리즘 15649번 ==[링크](https://www.acmicpc.net/problem/15649)==
3. N-Queens 문제
- N-Queens 문제는 NxN 체스판에서 N개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제
- 백준 알고리즘 9663번 ==[링크](https://www.acmicpc.net/problem/9663)==
4. 암호 만들기 문제
- 길이가 L인 암호를 만드는 문제
- 백준 알고리즘 1759번 ==[링크](https://www.acmicpc.net/problem/1759)==

> 백트래킹 알고리즘으로 풀어야 하는지 결정하는데 도움이 되는 특징
>
> 1. 탐색 공간이 크고, 조합적인 구조를 가진 경우
> 2. 퇴각 검색이 가능한 경우
> 3. 해답을 찾는 과정에서 결정을 순차적으로 내려야 하는 경우
> 4. 완전 탐색이 비효율적인 경우

## DFS(Depth-First Search)와 BFS(Breadth-First Search) 알고리즘

- DFS와 BFS는 그래프를 탐색하는 두 가지 대표적인 알고리즘으로 백트래킹 알고리즘과 함께 많이 사용된다.
- 

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

- 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나
- 현재 정점과 인접한 노드들 중 방문하지 않은 노드를 찾아 방문한다.이 때, 방문한 노드에서 다시 인접한 미방문 노드를 찾아 방문하는 과정을 반복하며, 더 이상 방문할 수 있는 인접 노드가 없으면 마지막으로 방문한 노드로 돌아가 인접 노드를 찾는 과정을 반복한다.
- 이런 방식으로 DFS는 가능한 한 깊이 있게 그래프를 탐색하는 특징을 가지고 있다. 그래서 이름이 '깊이 우선 탐색'인 것.
- DFS는 **스택(Stack)을 사용**하거나 **재귀 호출을 사용**하여 구현할 수 있다. 그래프의 복잡도에 따라서는 매우 효율적인 방법이 될 수 있지만, 최악의 경우 모든 노드를 방문해야 하므로 계산 복잡성이 높을 수 있다.
- DFS는 퍼즐 게임에서 해결책을 찾거나, 그래프에서 사이클을 찾는 등 다양한 문제 해결에 사용된다.

### **너비 우선 탐색(Breadth-First Search, BFS)**

- 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나
- BFS는 시작 정점에서 가장 가까운 정점을 먼저 방문하고, 그다음 가까운 정점을 방문하는 순서로 그래프를 탐색한다.
- BFS는 **큐(Queue)를 이용**하여 구현한다. 시작 정점을 방문하고 큐에 넣은 뒤, 큐에서 정점을 하나씩 꺼내면서 해당 정점의 인접한 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣고 방문처리를 한다. 이런 과정을 큐가 빌 때까지 반복한다.
- BFS는 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용할 수 있다. 또한, BFS는 모든 간선의 가중치가 동일할 때 최단 경로를 찾는 데 사용할 수 있다. 이와 같은 이유로 그래프의 모든 정점을 '최소한의 단계만에' 방문하고 싶을 때 사용한다.

### DFS vs BFS

| DFS | BFS |
| :-------------------------------------------: | :-------------------------------------------: |
|  |  |

1. **탐색 방식**
- DFS는 깊이를 우선으로 하여 가능한 한 멀리 있는 정점을 우선적으로 탐색하고, 더 이상 방문할 곳이 없을 때 이전 정점으로 돌아가 탐색을 계속하는 방식
- BFS는 너비를 우선으로 하여 한 정점에서 가능한 한 가까운 정점부터 탐색하는 방식
2. **사용하는 자료구조**
- DFS는 스택이나 재귀를 통해 구현한다
- BFS는 큐를 통해 구현한다
3. **적합한 사용 사례**
- DFS는 경로의 특성을 활용해 문제를 해결해야 하는 경우, 모든 노드를 방문해야 하는 경우에 적합하며 그래프의 깊이가 얕은 경우에 효과적
- BFS는 가장 짧은 경로를 찾아야 하는 경우(단, 가중치가 없는 경우)나 두 노드 사이의 최단 거리를 찾는 문제 등에 적합
4. **시간 복잡도**
- 둘 다 그래프의 모든 정점과 간선을 방문하므로 시간 복잡도는 동일하게 O(V+E)이다(V: 정점의 수, E: 간선의 수).
5. **공간 복잡도**
- DFS는 경로를 저장하기 위한 스택에 모든 노드를 저장할 수도 있기 때문에, 최악의 경우 공간 복잡도는 O(V)이다
- BFS는 방문해야 할 노드를 저장하기 위한 큐에 모든 노드를 저장하므로 공간 복잡도는 역시 O(V)이다
6. **특징**
- DFS는 경로 자체를 찾는 문제에서 유용하며, 모든 경로를 찾는 문제에서도 쓰인다
- BFS는 최단 경로를 찾는 문제, 또는 레벨(단계)별로 탐색해야 하는 문제에 사용된다

### DFS & BFS 문제

- 백준 알고리즘 1260번 ==[링크](https://www.acmicpc.net/problem/1260)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### DFS & BFS 문제 수도코드 예

1. 그래프 생성
   - 먼저, 그래프를 표현할 수 있는 자료구조를 생성한다. 이 문제에서는 인접 리스트를 사용할 수 있다. 각 노드와 그에 연결된 노드들의 목록을 저장한다.
2. 깊이 우선 탐색 (DFS)
   1. 주어진 시작점에서 출발하여 가능한 깊게 노드를 탐색한다.
   2. 각 노드에 방문했음을 표시하고, 그 노드에 연결된 노드들 중 아직 방문하지 않은 노드가 있다면 그 노드로 이동한다.
   3. 방문할 수 있는 노드가 더 이상 없다면 이전 노드로 돌아가 다른 방향을 탐색한다.
   4. 1 ~ 3 과정을 모든 노드를 방문할 때까지 반복한다.
3. 너비 우선 탐색 (BFS)
   1. 시작점에서 출발하여 연결된 노드들을 차례로 방문한다.
   2. 각 노드에 방문했음을 표시하고, 그 노드에 연결된 노드들을 방문 대기 목록에 추가한다.
   3. 방문 대기 목록에서 순서대로 노드를 뽑아 방문하며, 뽑은 노드에 연결된 노드들을 방문 대기 목록에 추가한다.
   4. 1 ~ 3 과정을 모든 노드를 방문할 때까지 반복한다.
4. 결과 출력
   - DFS와 BFS를 통해 얻은 방문 순서를 출력한다.

#### DFS & BFS 문제 소스코드 예

import java.util.*;

public class Main {

    static ArrayList<Integer>[] list; // 그래프를 표현할 인접 리스트
    static boolean[] check; // 노드 방문 여부를 나타내는 배열

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 정점의 개수
        int m = scanner.nextInt(); // 간선의 개수
        int v = scanner.nextInt(); // 탐색을 시작할 정점

        list = new ArrayList[n + 1]; // 인접 리스트 초기화

        for (int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<Integer>(); // 각 정점에 대한 인접 리스트 생성
        }

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            list[a].add(b); // a와 b 사이의 간선 추가
            list[b].add(a); // 양방향 간선이므로 b와 a 사이의 간선도 추가
        }

        // 정점별로 인접한 정점들을 오름차순으로 정렬
        for (int i = 1; i < n + 1; i++) {
            Collections.sort(list[i]);
        }

        check = new boolean[n + 1];
        dfs(v); // DFS 수행

        System.out.println();

        check = new boolean[n + 1];
        bfs(v); // BFS 수행

        scanner.close();
    }

    public static void dfs(int x) {
        if (check[x]) { // 이미 방문한 정점이라면 종료
            return;
        }

        check[x] = true; // 정점 방문 처리
        System.out.print(x + " "); // 정점 출력

        // 현재 정점과 인접한 정점들에 대해 재귀적으로 DFS 호출
        for (int y : list[x]) {
            if (!check[y]) { // 아직 방문하지 않은 정점이라면 DFS 호출
                dfs(y);
            }
        }
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start); // 시작 정점을 큐에 추가
        check[start] = true; // 시작 정점 방문 처리

        while (!queue.isEmpty()) {
            int x = queue.poll(); // 큐에서 정점 추출
            System.out.print(x + " "); // 정점 출력

            // 현재 정점과 인접한 정점들에 대해 순차적으로 처리
            for (int y : list[x]) {
                if (!check[y]) { // 아직 방문하지 않은 정점이라면
                    check[y] = true; // 정점 방문 처리
                    queue.add(y); // 해당 정점을 큐에 추가
                }
            }
        }
    }
}

### N과 M (1) 문제

- 백준 알고리즘 15649번 ==[링크](https://www.acmicpc.net/problem/15649)==
- N과 M (1) 문제는 순열 생성 문제로, 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제이며, 순열 생성 문제는 백트래킹 알고리즘을 사용하여 해결할 수 있다.
- 
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### N과 M (1) 문제 수도코드 예

1. 정수 N과 M을 입력 받는다.
2. 수열을 저장할 배열과 방문 여부를 체크할 배열을 생성한다.
3. 백트래킹 함수를 호출한다.
4. 백트래킹 함수 정의:
   1. 현재 수열의 길이가 M과 같다면, 수열을 출력한다.
   2. 아니라면, 1부터 N까지 반복하면서
      1. 해당 숫자를 아직 방문하지 않았다면, 방문했다고 체크하고, 수열에 추가한다.
      2. 다음 수를 결정하기 위해 재귀적으로 백트래킹 함수를 호출한다.
      3. 방문한 숫자를 다시 방문하지 않았다고 체크하고, 수열에서 제거한다.

#### N과 M (1) 문제 소스코드 예

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt(); // N과 M을 입력받는다
        M = scanner.nextInt();

        arr = new int[M]; // 길이 M의 수열을 저장할 배열
        visit = new boolean[N + 1]; // 방문 여부를 체크할 배열

        dfs(0); // 깊이우선탐색 시작
        System.out.println(sb);
    }

    static void dfs(int depth) {
        if (depth == M) { // 현재 수열의 길이가 M과 같다면 수열을 출력한다
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= N; i++) { // 1부터 N까지 반복하면서
            if (!visit[i]) { // 해당 숫자를 아직 방문하지 않았다면
                visit[i] = true; // 방문했다고 체크
                arr[depth] = i; // 수열에 추가
                dfs(depth + 1); // 다음 수를 결정하기 위해 재귀적으로 함수를 호출
                visit[i] = false; // 방문한 숫자를 다시 방문하지 않았다고 체크
            }
        }
    }
}

### N-Queens 문제

- 백준 알고리즘 9663번 ==[링크](https://www.acmicpc.net/problem/9663)==
- N-Queens 문제는 NxN 체스판에서 N개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제로, 백트래킹 알고리즘을 사용하여 해결할 수 있다.
- 
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### N-Queens 문제 수도코드 예

1. 결과값을 저장할 "result"라는 변수를 만들고, 0으로 초기화 한다.
2. N x N 크기의 체스판을 표현할 "board"라는 배열을 만든다.
3. "isSafe"라는 함수를 만든다. 이 함수는 주어진 위치에 퀸을 놓을 수 있는지 확인한다.
   - 각 열, 그리고 대각선에 이미 퀸이 놓여있는지 확인한다. 만약 퀸이 있다면, 해당 위치에 퀸을 놓을 수 없으므로 false를 반환한다.
   - 만약 퀸이 없다면, 해당 위치에 퀸을 놓을 수 있으므로 true를 반환한다.
4. "placeQueen"이라는 함수를 만든다. 이 함수는 퀸을 실제로 배치하고, 가능한 모든 위치에 대해 재귀적으로 호출하여 모든 가능한 해결책을 찾는다.
   - 현재 행이 체스판의 크기와 같다면 (즉, 모든 행에 퀸을 배치했다면), 유효한 해결책이 하나 추가된 것이므로 "result"를 1 증가시킨다.
   - 현재 행에 대해 각 열을 순회하면서, 해당 위치에 퀸을 놓을 수 있는지 "isSafe" 함수를 통해 확인한다.
   - 만약 퀸을 놓을 수 있다면, "board" 배열에 퀸의 위치를 저장하고, 다음 행에 퀸을 배치하기 위해 "placeQueen" 함수를 재귀적으로 호출한다.
5. "placeQueen" 함수를 첫 번째 행부터 호출하여 시작한다.
6. 모든 가능한 해결책을 찾은 후, "result"를 반환한다. "result"는 유효한 해결책의 총 수다.

#### N-Queens 문제 소스코드 예

2차원 배열로 구현한 N-Queens

import java.util.Scanner;

public class Main {
    private static int[][] board;
    private static int N;
    private static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 체스판의 크기 및 퀸의 개수 설정
        board = new int[N][N];
        placeQueen(0);
        System.out.println(result); // 가능한 배치의 수 출력
    }

    private static boolean isSafe(int currentRow, int currentCol) {
        // 현재 행까지의 모든 행을 확인한다.
        for (int i = 0; i < currentRow; i++) {
            // 같은 열에 퀸이 있는지 확인한다.
            // 체스의 퀸은 같은 열을 공격할 수 있기 때문에, 같은 열에 퀸이 있다면 현재 위치는 안전하지 않다.
            if (board[i][currentCol] == 1) {
                return false;
            }

            // 왼쪽 대각선에 퀸이 있는지 확인한다.
            // 체스의 퀸은 대각선 방향을 공격할 수 있기 때문에, 왼쪽 대각선에 퀸이 있다면 현재 위치는 안전하지 않다.
            // 대각선을 확인할 때는 범위를 넘어서지 않는지 확인해야 한다.
            if (currentCol - (currentRow - i) >= 0) {
                if (board[i][currentCol - (currentRow - i)] == 1) {
                    return false;
                }
            }

            // 오른쪽 대각선에 퀸이 있는지 확인한다.
            // 체스의 퀸은 대각선 방향을 공격할 수 있기 때문에, 오른쪽 대각선에 퀸이 있다면 현재 위치는 안전하지 않다.
            // 대각선을 확인할 때는 범위를 넘어서지 않는지 확인해야 한다.
            if (currentCol + (currentRow - i) < N) {
                if (board[i][currentCol + (currentRow - i)] == 1) {
                    return false;
                }
            }
        }

        // 같은 열 혹은 어떤 대각선에도 퀸이 없다면 현재 위치는 안전하다고 판단할 수 있다.
        return true;
    }

    private static void placeQueen(int row) {
        if (row == N) {
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(row, i)) {
                board[row][i] = 1;
                placeQueen(row + 1);
                board[row][i] = 0;
            }
        }
    }
}

---

1차원 배열로 구현한 N-Queens

import java.util.Scanner;

public class Main {
    private static int[] board;
    private static int N;
    private static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 체스판의 크기 및 퀸의 개수 설정
        board = new int[N];
        placeQueen(0);
        System.out.println(result); // 가능한 배치의 수 출력
    }

    private static boolean isSafe(int currentRow, int currentCol) {
        for (int i = 0; i < currentRow; i++) {
            // 같은 열에 다른 퀸이 있는지 확인한다.
            if (board[i] == currentCol) {
                return false; // 같은 열에 퀸이 있으면 안전하지 않으므로 false를 반환한다.
            }

            // 대각선 방향에 다른 퀸이 있는지 확인한다.
            // 대각선 방향에 퀸이 있으면, |currentRow - i| == |currentCol - board[i]|가 된다.
            if (Math.abs(currentRow - i) == Math.abs(currentCol - board[i])) {
                return false; // 대각선 방향에 퀸이 있으면 안전하지 않으므로 false를 반환한다.
            }
        }

        // 같은 열 혹은 대각선 방향에 다른 퀸이 없으면 안전하므로 true를 반환한다.
        return true;
    }
    private static void placeQueen(int row) {
        if (row == N) {
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(row, i)) {
                board[row] = i;
                placeQueen(row + 1);
            }
        }
    }
}

### 암호 만들기 문제

- 백준 알고리즘 1759번 ==[링크](https://www.acmicpc.net/problem/1759)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 암호 만들기 문제 수도코드 예

1. 암호로 사용될 문자의 개수 L과 총 문자의 개수 C를 입력받는다.
2. C개의 문자를 입력받아 사전 순으로 정렬한다.
3. 재귀 함수를 사용하여 가능한 모든 L 길이의 문자 조합을 찾는다.
    a. 조합이 L 길이에 도달하면, 모음과 자음의 개수를 확인한다.
    b. 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있으면, 해당 조합을 출력한다.
4. 모든 조합을 사전 순으로 출력한다.

#### 암호 문제 만들기 소스코드 예

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int L, C; // L은 암호의 길이, C는 주어진 문자의 개수
    static char[] candidates, password; // 사용 가능한 문자들과 암호를 저장할 배열
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        candidates = new char[C]; // 사용 가능한 문자들을 저장할 배열
        password = new char[L]; // 생성된 암호를 저장할 배열
        
        for (int i = 0; i < C; i++) {
            candidates[i] = sc.next().charAt(0); // 문자를 하나씩 입력받아 배열에 저장
        }
        
        Arrays.sort(candidates); // 사전 순으로 문자를 정렬
        generatePassword(0, 0); // 암호 생성 시작
    }
    
    public static void generatePassword(int start, int depth) {
        if (depth == L) {
            if (isValid(password)) { // 생성된 암호가 조건을 만족하는지 확인
                System.out.println(password); // 조건을 만족하는 암호 출력
            }
            return;
        }
        
        for (int i = start; i < C; i++) {
            password[depth] = candidates[i]; // 현재 위치에 문자를 설정
            generatePassword(i + 1, depth + 1); // 다음 문자를 설정하기 위해 재귀 호출
        }
    }
    
    public static boolean isValid(char[] arr) {
        int vowels = 0; // 모음의 개수
        int consonants = 0; // 자음의 개수
        for (char c : arr) {
            // 모음인지 자음인지 확인하여 각각의 개수를 셈
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowels++;
            } else {
                consonants++;
            }
        }
        // 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있는지 확인
        return vowels >= 1 && consonants >= 2;
    }
}