[코딩테스트] Java - 백트래킹

백트래킹

- 완전탐색: dfs, bfs처럼 데이터를 전부 확인하는 방법

- 백트래킹(backtracking): 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

- 유망함수(promising function): 특정 조건을 정하는 함수

 

(백트래킹 풀이법)

1. 유효한 해의 집합을 정의

2. 정의한 집합을 그래프로 표현

3. 유망함수 정의

4. 백트래킹을 통한 해 탐색

 

(부분 집합 합)

- 부분 집합 합(sum of subset): 1부터 N까지 숫자르 조합했을 때 합이 K가 되는 조합을 찾는 문제

- 유망함수1: 현재 조합으로 합이 K일 경우 탐색 중지

- 유망함수2: 해당 숫자를 조합하여 합이 K 이상이 되면 탐색 중지

 

(N-Queen)

- N-Queen: 체스의 퀸을 N x N 체스판에 N개 배치시 서로 공격할 수 없는 위치에 놓을 수 있는 방법의 수를 찾는 문제. 퀸은 상하좌우대각으로 이동 가능

- 유망함수: 퀸 추가시 동일 행이나 열, 대각선 방향에 중복된 퀸 존재시 탐색 중지

 

예제

(1부터 N까지 숫자 중 합이 K가 되는 조합)

- 유망함수1: 조합한 숫자의 합이 K일 경우 리스트에 추가

- 유망함수2: 조합한 숫자의 합이 10보다 크면 백트래킹

- 입력: N, K

- 출력: 합이 K가 되는 숫자들의 리스트(2차원 배열)

import java.util.ArrayList;

class Solution {
    private static ArrayList<ArrayList<Integer>> result;
    private static int n;
    private static void backtrack(int sum, ArrayList<Integer> selectedNums, int start) {
        if (sum == 10) {
            result.add(selectedNums);
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            if (sum + i <= 10) {
                ArrayList<Integer> list = new ArrayList<>(selectedNums);
                list.add(i);
                backtrack(sum + i, list, i + 1);
            }
        }
    }
    
    private static ArrayList<ArrayList<Integer>> solution(int N) {
        result = new ArrayList<>();
        n = N;
        
        backtrack(0, new ArrayList<>(), 1);
        return result;
    }
}

 

(스도쿠 퍼즐)

- 스도쿠 퍼즐: 9 x 9 스도쿠 보드를 다 채원 완성된 스도쿠 보드를 반환

- 스도쿠 퍼즐 조건1: 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야 함

- 스도쿠 퍼즐 조건2: 9 x 9 보드를 채울 9개의 작은 박스(3 x 3 크기)에도 1부터 9까지의 숫자가 한 번씩 나타나야 함

- 유망함수1: 해당 행에 넣으려는 숫자가 있는지 확인

- 유망함수2: 해당 열에 넣으려는 숫자가 있는지 확인

- 유망함수3:  해당 위치를 포함하는 3 x 3 박스에 넣으려는 숫자가 있는지 확인

 

- 입력: board(2차원 행렬의 스도쿠 퍼즐)

- 출력: 2차원 행렬

import java.util.Arrays;

class Solution {
    private static class Block {
        int i, j;
        public Block(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    
    private static int[][] Board;
    
    private static boolean isValid(int num, int row, int col) {
        return !(inRow(num, row) || inCol(num, col) || inBox(num, row, col));
    }
    
    private static boolean inRow(int num, int row) {
        return Arrays.stream(Board[row]).anyMatch(n -> n == num);
    }
    
    private static boolean inCol(int num, int col) {
        for (int i = 0; i < 9; i++) {
            if (Board[i][col] == num) return true;
        }
        return false;
    }
    
    private static boolean inBox(int num, int row, int col) {
        int boxRow = (row / 3) * 3;
        int boxCol = (col / 3) * 3;
        
        for (int i = boxRow; i < boxRow + 3; ++i) {
            for (int j = boxCol; j < boxCol + 3; ++j) {
                if (Board[i][j] == num) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private static Block findEmptyPosition() {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (Board[i][j] == 0) {
                    return new Block(i, j);
                }
            }
        }
        return null;
    }
    
    private static boolean findSolution() {
        Block emptyPos = findEmptyPosition();
        if (emptyPos == null)
            return true;
            
        int row = emptyPos.i;
        int col = emptyPos.j;
        
        for (int num = 1; num <= 9; num++) {
            if (isValid(num, row, col)) {
                Board[row][col] = num;
                if (findSolution()) {
                    return true;
                }
                Board[row][col] = 0;
            }
        }
        return false;
    }
    
    private static int[][] solution(int[][] board) {
        Board = board;
        findSolution();
        return board;
    }

}