[알고리즘] 완전 탐색

무식하게 풀기

무식하게 푼다(brute-force) 라는 것은 일반적으로 가능한 모든 경우의수를 일일이 나열하며 답을 찾는 방법을 의미한다. 이러한 알고리즘을 흔히 "완전 탐색" 이라고 부르며, 이는 컴퓨터의 빠른 계산 능력을 가장 잘 활용하는 알고리즘이라고 할 수 있다.

다만, 일반적으로 문제의 크기가 커질수록 경우의 수가 기하급수적으로 늘어나므로 완전 탐색을 적용할 수 없게 된다. 따라서 이 알고리즘은 문제의 크기가 그리 크지 않은 경우에 유용하게 사용할 수 있다.

재귀함수와 완전 탐색

일반적으로 완전 탐색은 재귀함수를 통해 쉽게 구현할 수 있다.

동전 뒤집기

5개의 동전이 있을 때, 다음과 같이 모든 가능한 동전의 상태를 출력하는 문제를 생각해보자.

앞 앞 앞 앞 앞
앞 앞 앞 앞 뒤
앞 앞 앞 뒤 앞
...
뒤 뒤 뒤 뒤 뒤

이를 다음과 같은 재귀 함수로 구현할 수 있다.

int coin[5]; // 0: 뒷면, 1: 앞면

void printCoin() {
    for (int i = 0; i < 5; i++) {
        printf("%s ", coin[i] ? "앞" : "뒤");
    }
    printf("\n");
}

// i번쨰 동전의 상태를 결정한다.
void filpCoin(int i) {
    // 마지막 동전까지 결정했다면 출력하고 종료한다.
    if (i == 5) {
        printCoin();
        return;
    }
    coin[i] = 1; // 앞면
    filpCoin(i + 1); // 다음 동전으로
    coin[i] = 0; // 뒷면
    filpCoin(i + 1); // 다음 동전으로
}

답의 순서와 형태 제한하기

경우의 수를 세는 문제에서 완전 탐색을 적용할 때 흔히 발생하는 실수 중 하나는 같은 답을 중복하여 세는 경우이다. 이러한 문제를 방지하기 위해, 특정한 순서 또는 형태의 답만 세도록 강제할 수 있다.

게임판 덮기

예를 들어, 다음과 같은 게임판의 빈 칸을 ㄱ자 모양의 블록을 통해 모두 덮는 경우의 수를 세는 문제를 생각해보자.

이 문제에서 블록을 놓는 순서는 중요하지 않다. 즉, 블록을 놓는 순서가 다르더라도 같은 모양이라면 같은 경우로 세어야 한다.

같은 경우를 중복으로 세지 않기 위해, 다음과 같이 블록을 놓는 순서를 제한할 수 있다.

• 블록을 놓을 때 빈 칸 중 가장 위, 그 중에서도 가장 왼쪽에 있는 칸에 놓는다.

이렇게 하면 한 답을 한 가지 방법으로밖에 생설할 수 없으므로, 중복으로 답을 세는 문제를 해결할 수 있다.

짝 짓기

또 다른 예로, N명의 학생을 2명씩 짝지어 팀을 만드는 경우의 수를 세는 문제를 생각해보자.

이 문제에서 다음 두 경우는 하나로 세어야 한다.

• (철수, 영희), (민수, 상현)
• (상현, 민수), (철수, 영희)

이 문제에서도 답의 형태를 제한하기 위해 우선 학생들에게 번호를 매길 수 있다. 여기서는 다음과 같이 답의 형태를 제한할 수 있다.

• 새로운 짝을 만들 때, 아직 짝이 지어지지 않은 학생 중에서 번호가 가장 작은 학생을 선택한다.

이런식으로 답을 생성하면 결과가 항상 정렬된 형태로 생성되므로, 같은 답을 중복하여 세지 않게 된다.

격자판 불 켜기

또한, 답의 순서 또는 형태를 제한하는 기법은 중복을 방지하기 위함 뿐만 아니라 탐색해야 할 경우의 수를 획기적으로 줄이는 방법으로도 사용될 수 있다.

위와 같은 격자판에 몇 개의 칸에만 불이 켜져있다. 이때, 각 칸을 누르면 그 칸과 상하좌우에 있는 칸의 불이 켜지거나 꺼진다. (즉, 켜져있으면 꺼지고, 꺼져있으면 켜진다.) 이때, 모든 불을 켜기 위해 눌러야 하는 횟수를 최소하하는 문제를 생각해보자.

이 문제를 모든 경우의 수를 따져가며 풀려고 하면 $2^{25}$개의 경우의 수가 나온다. 그러나, 칸을 누르는 순서가 중요하지 않다는 사실을 깨닫고 나면, 누르는 순서를 강제함으로써 경우의 수를 $2^{5}$개까지 줄일 수 있다. 이것이 어떻게 가능한지는 스스로 생각해보면 도움이 될 것이다.

CLOCKSYNC: 시계 맞추기

https://algospot.com/judge/problem/read/CLOCKSYNC

답 제한하기

조금만 생각해보면 이 문제에서 다음과 같은 사실을 발견할 수 있다.

• 스위치를 누르는 순서는 중요하지 않다.
• 한 스위치를 4번 이상 누르는 것은 의미가 없다.

따라서, 다음과 같이 답의 형태를 제한할 수 있다.

• 0번 스위치부터 9번 스위치까지 순서대로 누른다.
• 한 스위치를 누르는 횟수는 0~3이다.

코드

char linked[10][16] = {
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};

int clocks[16];

// 시계가 모두 12시를 가리키고 있는지 확인한다.
int areAligned() {
    for (int i = 0; i < 16; i++) {
        if (clocks[i] != 12) {
            return 0;
        }
    }
    return 1;
}

// swtch번 스위치를 누른다.
void push(int swtch) {
    for (int clock = 0; clock < 16; clock++) {
        if (linked[swtch][clock] == 'x') {
            clocks[clock] += 3;
            if (clocks[clock] == 15) {
                clocks[clock] = 3;
            }
        }
    }
}

// 이번에 누를 스위치의 번호 swtch가 주어질 때,
// 남은 스위치들을 눌러서 모든 시계를 12시로 맞출 수 있는 최소 횟수를 반환한다.
int solve(int swtch) {
    // 모든 스위치를 눌러봤으면, 남은 시계들이 전부 12시를 가리키는지 확인한다.
    if (swtch == 10) return areAligned() ? 0 : INF;

    // swtch번 스위치를 0~3번 눌러본다.
    int ret = INF;
    for (int cnt = 0; cnt < 4; cnt++) {
        ret = min(ret, cnt + solve(swtch + 1));
        push(swtch);
    }
    return ret;
}