백트래킹(Backtracking)

1. 백트래킹(Backtracking)이란?

- 백트래킹은 문제의 가능한 모든 해를 탐색하는 과정에서 조건을 만족하지 않는 경로를 조기에 포기하여 탐색 범위를 줄이는 기법이다.

- 그리디나 단순 브루트포스와 달리 백트래킹은 모든 배치를 시도하지만 조건을 위반하는 경우 탐색을 중단하고 되돌아간다.

 

1-1. 핵심 아이디어

- 문제 분할: 문제를 여러 하위 문제로 나눈 후 각 단계에서 선택할 수 있는 후보를 탐색한다.

- 가지치기: 현재까지의 선택이 문제의 조건을 만족하는지 검사하고 만족하지 않으면 바로 이전 상태로 돌아가 다른 후보를 탐색한다.

 

1-2. 백트래킹 장단점

- 장점: 문제의 해 공간이 크더라도 불필요한 경로를 빠르게 배제한다, 복잡한 문제도 재귀 호출과 조건 검사를 통해 간결한 코드로 구현 가능하다.

- 단점: 최악의 경우 모든 경우를 탐색한다, 문제에 따라 최적화방법이 결합되지 않으면 비효율적일 수 있다.

 

2. 백트래킹 활용 문제

2-1. N-Queen 문제

- N x N 체스판위에 N개의 퀸을 서로 공격하지 않도록 놓는 문제이다.

- 퀸은 같은 행, 열, 대각선 상에 있을 때 서로 공격할 수 있다.

public class NQueen {
    // 모든 해의 가짓수를 전역 변수로 관리
    static int count = 0;

    // 현재 위치에 퀸을 놓을 수 있는지 체크하는 함수
    public static boolean isSafe(int[][] board, int row, int col, int n) {
        // 같은 열에 있는 퀸 검사 (위쪽만 확인)
        for(int i = 0; i < row; i++) {
            if(board[i][col] == n) {
                return false;
            }
        }

        // 왼쪽 대각선 위쪽 검사
        for(int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if(board[i][j] == n) {
                return false;
            }
        }

        // 오른쪽 대각선 위쪽 검사
        for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    // 백트래킹을 이용해 N-Queen 문제의 모든 해를 탐색하는 함수
    public static void solveNQueen(int[][] board, int row, int n) {
        // 기저 조건: 모든 행에 퀸을 놓았다면 해를 찾은 것
        if(row == n) {
            count++;
            return;
        }

        // 현재 행의 모든 열에 대해 퀸 놓기
        for(int col = 0; col < row; col++) {
            if(isSafe(board, row, col, n)) {
                board[row][col] = 1; // 퀸 놓기
                solveNQueen(board, col+1, n); // 다음행으로 진행
                board[row][col] = 0; // 백트래킹: 놓은 퀸 제거
            }
        }
    }

    public static void main(String[] args) {
        // 예제 데이터
        int n = 4;

        int[][] board = new int[n][n];
        solveNQueen(board, 0, n);

        System.out.println(count);
    }
}

 

2-2. Word Search 문제

- 주어진 2차원 보드에서 특정 단어가 존재하는지 확인하는 문제이다.

- 단어는 인접(상하좌우)한 칸들로 연결되어야 하며, 같은 칸을 두 번 이상 사용할 수 없다.

public class WordSearch {

    // 4방향 이동: 위, 오른쪽, 아래, 왼쪽
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    // 주어진 보드에서 단어가 존재하는지 확인하는 함수
    public static boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];

        // 보드의 모든 칸을 시작점으로 DFS 돌리기
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(dfs(board, word, 0, i, j, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    // DFS로 board[x][y]에서 시작하여 단어의 index번째 문자부터 탐색
    private static boolean dfs(int[][] board, String word, int index, int x, int y, boolean[][] visited) {
        // 기저 조건: 단어의 모든 문자를 찾은 경우
        if(index == word.length()) {
            return true;
        }

        // 범위 체크, 방문 여부, 현재 문자 일치 여부 확인
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || board[x][y] != word.charAt(index)) {
            return false;
        }

        // 현재 칸 방문 처리
        visited[x][y] = true;

        // 4방향(상, 우, 하, 좌) 탐색
        for (int dir = 0; dir < 4; dir++) {
            int newX = x + dx[dir];
            int newY = y + dy[dir];
            if (dfs(board, word, index + 1, newX, newY, visited)) {
                return true;
            }
        }

        // 백트래킹: 현재 칸 방문 취소
        visited[x][y] = false;
        return false;

    }

    public static void main(String[] args) {
        // 예제 데이터
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word = "ABCCED";

        boolean result = exist(board, word);

        // 출력: true
        System.out.println(result);
    }
}