브루트포스(Brute Force)

브루트포스(Brute Force), 또는 완전 탐색은 가능한 답 후보를 빠짐없이 만들고 조건에 맞는지 검사하는 방법이다. “모든 후보를 본다”는 말만으로 구현이 정해지지 않는다. 후보를 어떤 순서로 만들지, 같은 답을 두 번 세지 않을지, 언제 더 내려가지 않아도 되는지가 핵심이다. 입력 크기가 작거나, 최적화된 알고리즘의 정답을 검증할 기준 구현이 필요할 때 특히 유용하다.

어떤 순서로 후보를 검사할까?

• 배열에서 하나씩 확인하는 순차 탐색은 후보가 n개면 최대 n개를 본다.
• 조합·순열은 선택지를 재귀나 중첩 반복문으로 펼칠 수 있다. n개 중 k개를 고르면 후보는 C(n,k)개다.
• DFS와 BFS는 탐색 순서다. 모든 상태를 방문하면 완전 탐색이고, 조건을 이용해 불가능한 가지를 버리면 백트래킹이다. BFS를 쓴다고 자동으로 완전 탐색이 되는 것은 아니다.

문제 해결방법

1. 한 답을 이루는 선택들을 정의한다. 예를 들어 학생 짝짓기는 “아직 짝이 없는 첫 학생의 짝”을 한 번의 선택으로 삼는다.
2. 선택마다 가능한 값과 제약 조건을 정한다. 친구가 아닌 학생과는 짝을 만들지 않는다.
3. 선택을 모두 끝냈을 때만 완성된 답을 세고, 이전 선택 상태로 복원한 뒤 다음 후보를 검사한다.

완전탐색 레시피

1. 최대 입력에서 후보가 몇 개인지 먼저 계산한다. 실제 시간에는 후보 생성·조건 검사·문자열 복사 비용도 들어가므로 답의 개수와 정확히 비례한다고 단정하지 않는다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3. 그 중하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성 했으므로, 이것을 기저사례로 선택해 처리해야한다.

flowchart TD
  A[현재 선택 상태] --> B{완성했는가?}
  B -- 예 --> C[조건 확인 후 답 1개 기록]
  B -- 아니오 --> D[다음 선택 후보 열거]
  D --> E{제약을 만족하는가?}
  E -- 아니오 --> D
  E -- 예 --> F[선택하고 재귀 호출]
  F --> G[선택을 되돌림]
  G --> D

아래 한 파일에는 네 가지 탐색 예제가 섞여 있다. sum은 재귀의 종료 조건, sum4와 pick은 중복 없는 조합, Boggle은 격자 경로, Picnic과 BoardCover는 상태를 바꾸고 되돌리는 백트래킹을 보여준다. 각각의 후보 수와 종료 조건이 다르므로 같은 복잡도 하나로 묶지 않는다.

import java.util.List;
import java.util.Stack;

public class BruteForce {
    public static void main(String[] args) {
				System.out.println(sum(5));
        System.out.println(recursiveSum(5));
        System.out.println(sum4(7));
        pick(7, new Stack<>(),5);

        Boggle boggle = new Boggle();
        String[][] board = new String[][]{
                {"U", "R" ,"L", "P", "M"},
                {"X", "P", "R", "E", "T"},
                {"G", "I", "A", "E", "T"},
                {"X", "T", "N", "Z" ,"Y"},
                {"X", "O", "Q", "R", "S"}

        };

        boolean checked = false;
        for (int i = 0 ; i <= 4; i ++) {
            for (int j = 0; j <= 4; j ++) {
                if (boggle.hasWord(i, j, "PRETTY", board)) {
                    checked = true;
                }
                if (checked) {
                    break;
                }
            }
        }
        System.out.println(checked ? "YES" : "NO");

        Picnic picnic = new Picnic(6, 10, "0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5".split(" "));

        int couple = picnic.countPairings(new boolean[6]);
        System.out.println(couple);

        BoardCover boardCover = new BoardCover();
        char[][] test = new char[][] {
                {'#','#','#','#','#','#','#','#','#','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','.','.','.','.','.','.','.','.','#'},
                {'#','#','#','#','#','#','#','#','#','#'}
        };
        int[][] boards = new int[test.length][test[0].length];
        for (int i = 0 ; i < test.length; i++) {
            for (int j = 0; j < test[i].length; j++) {
                boards[i][j] = (test[i][j] == '#') ? 1 : 0;
            }
        }

        int ans = boardCover.cover(boards);
        System.out.println(ans);
    }
    //1부터 n까지의 합을 계산하는 반복함수
    //필수조건 n >= 1
    //결과 : 1부터 n까지의 합 반환
    private static int sum(int n) {
        int ret = 0;
        for (int i = 1; i <= n; ++i) {
            ret += i;
        }
        return  ret;
    }
    //1부터 n까지의 합을 계산하는 재귀 함수
    //필수조건 n >= 1
    //결과 : 1부터 n까지의 합 반환
    private static int recursiveSum(int n) {
        if (n == 1) {
            return 1; //더 이상 쪼개지지 않을 때
        }
        return n + recursiveSum(n-1);
    }

    //n개의 원소 중 4개를 고르는 경우
    public static int sum4(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        count++;
                        System.out.println(i +", " + j +", " + k + ", " + l);
                    }
                }
            }
        }
        return count;
    }
    //n : 전체 원소 수
    //picked : 지금까지 고른 원소들의 번호
    //toPick : 몇개의 원소를 고를 수
    public static void pick(int n, Stack<Integer> picked, int toPick) {
        //더 고를 원소가 없을 때 고른 원소들을 출력
        if (toPick == 0) {
            System.out.println(picked);
            return;
        }
        //가장 작은 번호를 계산
        int smallest = picked.isEmpty() ? 0 : picked.peek() + 1;

        for (int next = smallest; next < n; ++next) {
            picked.push(next);
            pick(n, picked, toPick - 1);
            picked.pop();
        }
    }

    /**
     * 보글 게임
     * 5 X 5 크기 알파뱃 격자를 가지고 하는 게임
     * 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것.
     * 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있음.
     * 주어진 칸에서 시작하여 특정 단어를 찾을 수 있는지 확인하는 문제
     * https://algospot.com/judge/problem/read/BOGGLE
     * O(8^n)
     * 단어의 길이가 짧을 때 완전 탐색으로 해결 가능.
     */
    private static class Boggle {
        private static final int[] DX = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
        private static final int[] DY = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};

        public boolean hasWord(int y, int x, String word, String[][] board) {

            //1. 시작 위치가 범위 밖이면 무조건 실패
            if (word.isEmpty() || isRange(y, x, board)) {
                return false;
            }
            //2. 첫 글자가 일치하지 않으면 실패
            if (board[y][x].charAt(0) != word.charAt(0)) {
                return false;
            }
            //단어길이가 1이면 성공 리턴
            if (word.length() == 1) {
                return true;
            }

            //인접한 여덟 칸을 검사
            for (int direction = 0 ; direction < 8; direction++) {
                int nextY = y + DY[direction];
                int nextX = x + DX[direction];
                //다음 칸 검사
                if (hasWord(nextY, nextX, word.substring(1), board)) {
                    return true;
                }
            }
            return false;
        }
        private boolean isRange(int y, int x, String[][] board) {
            return y < 0 || y >= board.length || x < 0 || x >= board[y].length;
        }
    }

    /**
     *소풍
     * 두명식 짝을만듬
     * 항상 서로 친구인 학생들끼리 짝
     * 짝이 되는 학생들이 일부만 다르더라도 다른방법.
     */
    private static class Picnic {

        private boolean[][] friends;
        private int n;
        public Picnic(int std, int couple, String[] matching) {
            this.n = std;
            if (matching.length != 2 * couple) {
                throw new IllegalArgumentException("친구 쌍의 수가 일치하지 않습니다");
            }
            this.friends = new boolean[std][std];
            for (int i = 0; i < matching.length - 1; i += 2) {
                int a = Integer.parseInt(matching[i]);
                int b = Integer.parseInt(matching[i+1]);
                friends[a][b] = true;
                friends[b][a] = true;
            }
        }

        public int countPairings(boolean[] taken) {
            //1.남은 학생들 중 가장 번호가 빠른 학생을 찾음
            int firstFree = -1;
            for (int i = 0; i < n; i++) {
                if (!taken[i]) {
                    firstFree = i;
                    break;
                }
            }

            //2. 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료
            if (firstFree == -1) {
                return 1;
            }

            int ret = 0;

            //해당 학생과 짝지을 학생을 결정
            for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
                if (!taken[pairWith] && friends[firstFree][pairWith]) {
                    taken[firstFree] = taken[pairWith] = true;
                    ret += countPairings(taken);
                    taken[firstFree] = taken[pairWith] = false;
                }
            }
            return ret;
        }
    }

    public static class BoardCover {
        private static final int[][][] COVER_TYPE_YX = new int[][][] { //4,3,2
                {{0,0}, {1, 0}, {0,1}},
                {{0,0}, {0, 1}, {1,1}},
                {{0,0}, {1, 0}, {1,1}},
                {{0,0}, {1, 0}, {1,-1}}
        };
        //세 칸을 모두 검사한 뒤에만 덮는다. 실패한 배치는 보드를 바꾸지 않는다.
        private boolean canPlace(int[][] board, int y, int x, int type) {
            for (int[] offset : COVER_TYPE_YX[type]) {
                int ny = y + offset[0];
                int nx = x + offset[1];
                if (ny < 0 || ny >= board.length || nx < 0 || nx >= board[ny].length || board[ny][nx] != 0) {
                    return false;
                }
            }
            return true;
        }

        private void place(int[][] board, int y, int x, int type, int value) {
            for (int[] offset : COVER_TYPE_YX[type]) {
                board[y + offset[0]][x + offset[1]] = value;
            }
        }

        //board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환
        //board[i][j] = 1 이면 덮인 칸 혹은 검은 칸
        //board[i][j] = 0 이면 덮이지 않은 칸
        public int cover(int[][] board) {
            //아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
            int y = -1;
            int x = -1;
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (board[i][j] == 0) { //가장 먼저 덮을 칸 찾기
                        y = i;
                        x = j;
                        break;
                    }
                }
                if (y != -1) { //루프 탈출
                    break;
                }
            }

            //모든 칸이 채워졌으면 1을 반환
            if (y == -1) {
                return 1;
            }

            int ret = 0;

            for (int type = 0; type < 4; type++) {
                //만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출
                if (canPlace(board, y, x, type)) {
                    place(board, y, x, type, 1);
                    ret += cover(board);
                    place(board, y, x, type, 0);
                }
            }
            return ret;
        }
    }
}

1부터 n까지의 합: 종료 조건부터 확인하기

sum(5)는 반복문이 1, 2, 3, 4, 5를 한 번씩 더해 15를 만든다. recursiveSum(5)는 5 + recursiveSum(4)로 문제 크기를 하나 줄이고, recursiveSum(1)에서 멈춘다. 호출 깊이가 n이므로 두 함수 모두 시간은 O(n)이지만 재귀 버전은 호출 스택에 O(n) 공간을 더 쓴다. 코드의 전제는 n >= 1이다. 0을 넣으면 재귀 함수는 -1, -2, ...로 계속 내려가므로 실무 코드라면 입력을 검증하거나 n == 0을 기저 사례로 바꿔야 한다.

조합: 같은 답을 다시 세지 않기

sum4(n)의 네 반복문은 i < j < k < l이라는 불변식을 유지한다. 따라서 {0, 1, 2, 3}을 네 개 고르는 한 가지 답은 한 번만 출력되고 순서만 다른 선택은 생기지 않는다. 후보 수는 C(n,4) = n(n-1)(n-2)(n-3)/24이므로 시간은 O(n⁴)이고, n < 4이면 후보가 없다.

pick(n, picked, toPick)은 같은 원리를 재귀로 일반화한다. picked가 오름차순이고 아직 고를 수 있는 숫자가 마지막 원소보다 크다는 것이 불변식이다. picked.push(next)로 한 후보를 추가하고 재귀에서 돌아온 뒤 pop()으로 되돌린다. 되돌리지 않으면 다음 가지가 앞 가지의 값을 공유해 잘못된 조합을 만든다. n=4, toPick=2라면 [0,1], [0,2], [0,3], [1,2], [1,3], [2,3]의 여섯 조합이 나온다. 유효 입력은 0 <= toPick <= n이며, 모든 조합을 실제로 출력하면 최소 C(n,k) × k개의 값을 써야 한다.

보글: 위치와 남은 접미사가 상태

hasWord(y, x, word, board)가 답하는 질문은 “현재 칸 (y,x)에서 남은 단어를 만들 수 있는가?”이다. 범위 밖이거나 첫 글자가 다르면 즉시 실패한다. 한 글자만 남고 일치했다면 성공한다. 그 외에는 서로 다른 여덟 방향 중 하나라도 나머지 글자를 만들면 성공한다. 기존 방향 배열에는 왼쪽 위가 중복되고 오른쪽 위·왼쪽·아래가 빠져 있었으므로 여덟 방향을 바로잡았다. 직사각형 격자에서도 동작하도록 각 행의 길이로 경계를 검사한다.

단어 길이를 L이라 하면 한 출발점의 최악 탐색은 대략 O(8^(L-1))개의 경로다. 여기서는 substring(1)이 매번 남은 문자를 복사할 수 있으므로 실제 비용은 경로 수만으로 표현하기 어렵다. 이 코드는 완전 탐색을 설명하기 위한 예제이며 Algospot 제출 제한에는 그대로 적합하지 않다. 실제 제출에서는 단어 전체와 현재 인덱스를 전달하고 (행, 열, 글자 인덱스)의 결과를 메모이제이션하여 같은 부분 문제를 다시 풀지 않도록 해야 한다. 같은 칸의 재사용 가능 여부도 문제마다 다르다. 이 코드에 적힌 Algospot BOGGLE 규칙은 재사용을 허용하므로 방문 배열이 없다. 재사용이 금지된 퍼즐에서는 방문 표시와 복원이 필요하다.

소풍: 가장 빠른 미배정 학생을 고르는 이유

countPairings은 아직 짝이 없는 학생 중 번호가 가장 작은 firstFree를 찾는다. 이 학생에게 친구인 상대를 붙여 내려가면 같은 짝짓기를 (0,1)부터 시작한 경우와 (2,3)부터 시작한 경우로 중복해서 세지 않는다. 짝을 정할 때 taken의 두 칸을 true로 바꾸고 돌아온 뒤 반드시 false로 복원한다. 모두 배정되면 완성된 방법 한 가지이므로 1을 반환한다. 친구 쌍이 m개라면 입력은 정확히 2m개 숫자여야 하고, 친구 행렬 크기는 학생 수로 잡아야 한다. 기존 코드는 쌍의 수로 행렬을 만들고 입력 인덱스를 한 칸씩 이동해 서로 다른 쌍을 잘못 읽었다.

친구 관계가 모두 가능하고 학생 수가 짝수 n이라면 방법의 최대 개수는 (n-1) × (n-3) × ... × 1이다. 친구 제약은 가지를 줄이지만 최악의 경우는 여전히 빠르게 커진다. 학생 수가 홀수면 완전한 짝짓기는 없으므로 0이 나와야 한다.

보드 덮기: 배치 가능성 검사와 복원 분리

cover는 아직 비어 있는 칸 중 가장 위·왼쪽 칸을 고른다. 그 칸을 포함하는 네 종류의 ㄱ자 블록만 시도하면 놓는 순서가 다른 같은 덮개 구성이 중복되지 않는다. canPlace는 세 칸이 모두 보드 안의 빈 칸인지 확인하고, 가능한 경우에만 place(..., 1)로 덮는다. 재귀 호출 뒤 place(..., 0)으로 원상 복구하므로 다음 블록 모양은 같은 보드 상태에서 출발한다. 기존 set은 실패하는 배치에서도 보드를 먼저 바꾸고 나중에 반대로 호출해 복원했기 때문에 상태 추적이 어려웠다. 또한 예제의 보드는 각 행이 9칸인데 10칸짜리 배열을 채우려 해 범위 오류가 났다.

빈 칸 수가 3의 배수가 아니면 세 칸짜리 블록으로 모두 덮을 수 없으므로 재귀 전에 0을 반환하도록 최적화할 수 있다. 비어 있는 칸이 하나도 없으면 빈 배치도 완성된 방법 한 가지이므로 1을 반환한다. 각 재귀 단계에서 네 모양을 시도하므로 매우 거친 상한은 빈 칸 수를 E라 할 때 O(4^(E/3))이다. 실제로는 겹침과 경계 검사로 많은 가지가 사라진다. 큰 보드에는 그대로 쓰기 어렵고, 대칭 제거·메모이제이션 등 추가 전략이 필요하다.

참고: Algospot BOGGLE 문제. 문제의 칸 재사용 조건을 확인하고 다른 보글 변형에 그대로 적용하지 않는다.