# 백트래킹(Backtracking)

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

## 백트랙킹과 재귀호출


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

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

---

## 백트랙킹 예시
1. 미로 찾기 문제: 복잡한 갈랫길에서의 길을 찾는 문제 (DFS)
> 
2. 순열 생성 문제: 주어진 집합의 모든 순열을 생성하는 문제
> 
3. N-Queens 문제: N-Queens 문제는 NxN 체스판에서 N개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제
> 

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

### 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를 통해 얻은 방문 순서를 출력한다.

#### 소스코드 해답 예

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); // 해당 정점을 큐에 추가
                }
            }
        }
    }
}

---

### 수열 문제 1

- 백준 알고리즘 15651번 ==[링크](https://www.acmicpc.net/problem/15651)==

#### 수도코드 해답 예

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

#### 소스코드 해답 예

import java.io.IOException;
import java.util.*;
public class Main {
    static int N, M;
    static int[] arr;
    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의 수열을 저장할 배열

        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까지 반복하면서
            arr[depth] = i; // 수열에 추가
            dfs(depth + 1); // 다음 수를 결정하기 위해 재귀적으로 함수를 호출
        }
    }
}

---

### 순열 문제 2

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

#### 수도코드 해답 예

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

#### 소스코드 해답 예

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)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 수도코드 해답 예

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

#### 소스코드 해답 예

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 boolean isSafe(int currentRow, int currentCol) {
        for (int i = 0; i < currentRow; i++) {
            if (board[i] == currentCol || Math.abs(currentRow - i) == Math.abs(currentCol - board[i])) {
                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;
                placeQueen(row + 1);
            }
        }
    }
}

# 탐색 알고리즘

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


---
### **깊이 우선 탐색(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는 최단 경로를 찾는 문제, 또는 레벨(단계)별로 탐색해야 하는 문제에 사용된다

---

## 과제 : 백준 알고리즘 15650번 풀어보기

- 백준 알고리즘 15650번 ==[링크](https://www.acmicpc.net/problem/15650)==

---

###### tags: `과외(하희영)`