[03 알고리즘 설계 패러다임] 6. 무식하게 풀기

1. 도입

 

프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽습니다. 이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어봅시다. 무식하게 풀 수 있을까?

 

흔히 전산학에서 '무식하게 푼다(brute-force)'는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부릅니다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법입니다.

 

실제로 프로그래밍 대회에서도 프로그램을 빠르고 정확하게 구현하는 능력을 검증하기 위해 입력의 크기를 작게 제한한 문제들이 흔히 출제되며, 완전 탐색은 더 빠른 알고리즘의 기반이 되기도 하기 때문에 완전 탐색에 대해 잘 익혀둘 필요가 있습니다.

 

2. 재귀 호출과 완전 탐색

 

재귀 호출

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킵니다. 이렇게 들으면 꽤나 쓸데없이 보이지만 재귀 호출은 다양한 알고리즘을 구현하는 데 매우 유용하게 사용할 수 있는 도구입니다.

 

재귀 호출의 기초적인 성질을 이해하기 위해 가장 간단한 반복문을 재귀 함수로 바꿔 구현해 봅시다. 아래 코드는 자연수 n이 주어졌을 때 1부터 n까지의 합을 반환하는 함수 sum()의 구현을 보여줍니다. 이 함수를 어떻게 하면 재귀 호출을 이용하도록 바꿀 수 있을까요?

// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int sum(int n) {
    int ret = 0;
    for(int i = 1; i <= n; ++i) {
        ret += i;
    }
    return ret;
}

// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
    if(n == 1) return 1; // 더이상 쪼개지지 않을 때
    return n + recursiveSum(n-1);
}

 

n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 합시다. 재귀 호출을 이용하기 위해서는 이 조각 중 하나를 떼내어 자신이 해결하고, 나머지 조각들은 자기 자신을 호출해 해결해야 합니다. 이 조각 중에서 n만 따로 빼내기로 합시다. 그러면 1부터 n-1 까지의 조각들이 남는데, 이들을 모두 처리한 결과는 다름아닌 1부터 n-1 까지의 합입니다. 따라서 자기 자신을 호출해 n-1까지의 합을 구한 뒤, 여기에 n을 더하면 우리가 원하는 답이 됩니다.

 

한 가지 유의할 것은 n개의 조각 중 n이 아니라 1을 빼냈을 경우 이런 방법으로 문제를 해결할 수 없다는 것입니다. (역방향) 1을 빼고 나면 2부터 n까지의 합이 남는데, 이것은 1부터 n까지의 합을 구한다는 원래 문제와는 다른 형태이고 따라서 sum()을 호출해 계산할 수 없기 때문입니다.

 

recursiveSum()은 재귀 호출을 이용해 sum()을 구현한 함수입니다. recursiveSum() 함수의 첫 줄에 있는 if문에 주목해 봅시다. 이 조건문이 없으면 이 함수가 제대로 동작하지 않을 것임은 자명합니다. n = 1이면 조각이 하나뿐이니, 한 개를 빼고 나면 더이상 처리할 작업이 없으니까요. 모든 재귀 함수는 이와 같이 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 합니다.

 

기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야 합니다.

 

재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있습니다. 때문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구입니다.

 

3. 문제: 소풍 (문제 ID: PICNIC, 난이도: 하)

 

https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

4. 풀이: 소풍

 

완전 탐색

이렇게 가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 조합을 모두 만들어 보는 것입니다. 재귀 호출을 이용해 코드를 작성해 봅시다.

재귀 호출을 이용해 문제를 해결하려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나누어야 합니다. 여기서는 전체 문제를 n/2 개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 주는 것으로 하지요. 이때 문제의 형태는 '아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라'가 됩니다. 명단에서 서로 친구인 두 학생을 찾아 이들을 짝지어 주고나면 남은 학생들을 짝지어 주는 문제도 원래 문제와 같은 형태가 되니까요.

 

<잘못된 재귀 호출 코드>

int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
  // 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
  bool finished = true;
  for(int i = 0; i < n; ++i) if(!taken[i]) finished = false;
  if(finished) return 1;
  int ret = 0;
  // 서로 친구인 두 학생을 찾아 짝을 지어 준다.
  for(int i = 0; i < n; ++i) {
     for(int j = 0; j < n; ++j) {
       if(!taken[i] && !taken[j] && areFriends[i][j]) {
         taken[i] = taken[j] = true;
         ret += countPairings(taken);
         taken[i] = taken[j] = false;
       }
     }
  }
  return ret;
}

 

<결과 출력>

2
24
192

 

중복으로 세는 문제

위 코드를 곰곰히 들여다 보면 두 가지 문제점을 찾을 수 있습니다.

 

• 같은 학생 쌍을 두 번 짝지어 줍니다. 예를 들어 (0, 1)과 (1, 0)을 따로 세고 있습니다.
• 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있습니다. 예를 들어 (0, 1) 후에 (2, 3)을 짝지어 주는 것과 (2, 3) 후에 (0, 1)을 짝지어주는 것은 완전히 같은 방법인데 다른 경우로 세고 있지요.

실질적으로 같은 답을 중복으로 세는 이런 상황은 경우의 수를 다룰 때 굉장히 흔하게 마주칩니다. 이 상황을 해결하기 위해 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것입니다. 흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있습니다. 예를 들어 (2, 3), (0, 1) 이나 (1, 0), (2, 3) 은 세지 않지만 (0, 1), (2, 3)은 세는 것이죠.

이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 됩니다. 이렇게 하면 앞의 두 가지 문제를 모두 해결할 수 있음을 쉽게 알 수 있습니다. 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일 수 밖에 없기 때문에 (1,0)과 같은 짝은 나올 수 없습니다. 또한 항상 번호가 가장 빠른 학생부터 짝을 짓기 때문에 (2, 3), (0, 1)의 순서로 짝을 지어줄 일도 없지요. 다음 코드는 이러한 알고리즘의 구현을 보여줍니다.

 

int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
  // 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
  int firstFree = -1;
  for(int i=0;i<n;++i) {
    if(!taken[i]) {
      firstFree = i;
      break;
    }
  }
  
  // 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
  if(firstFree == -1) return 1;
  int ret = 0;
  // 이 학생과 짝지을 학생을 결정한다.
  for(int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
    if(!taken[pairWith] && areFriends[firstFree][pairWith]) {
      taken[firstFree] = taken[pairWith] = true;
      ret += countPairings(taken);
      taken[firstFree] = taken[pairWith] = false;
    }
  }
  return ret;
}

 

답의 수의 상한

모든 답을 생성해 가며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸립니다. 따라서 실제로 프로그램을 짜기 전에 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는 데 시간이 얼마나 오래 걸릴지를 확인해야겠지요. 이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 친구인 경우입니다. 이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 아홉명이고, 그 다음 학생이 선택할 수 있는 짝은 일곱 명입니다. 결국 최종 답의 개수는 9 * 7 * 5 * 3 * 1 = 945 가 된다는 것을 알 수 있지요.

 

5. 문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

 

https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

6. 풀이: 게임판 덮기

 

이 문제도 경우의 수를 세는 것이니만큼, 게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 해결할 수 있습니다. 우선 입력으로 주어진 게임판에서 흰 칸의 수가 3의 배수가 아닐 경우에는 무조건 답이 없으니 이 부분을 따로 처리하도록 합시다. 이 외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 합시다. 재귀 함수는 주어진 게임판에 블록을 한개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하면 되겠지요.

 

중복으로 세는 문제

그러나 이런 식으로 덮을 수 있는 방법의 수를 셀 수는 없다는 것을 우리는 잘 알고 있습니다. 블록을 놓는 순서는 이 문제에서 중요하지 않은데, 방금 설명한 방식으로는 같은 배치도 블록을 놓는 순서에 따라서 여러 번 세기 때문이지요. 따라서 특정한 순서대로 답을 생성하도록 강제할 필요가 있습니다.

가장 간편한 방법은 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 것입니다. 이렇게 하면 한 답을 한 가지 방법으로밖에 생성할 수 없으므로 중복으로 세는 문제를 해결할 수 있습니다. 

우리는 항상 빈 칸 중에서 가장 위, 그 중에서도 가장 왼쪽에 있는 칸을 처음 채운다고 가정하기 때문에 그 왼쪽과 위에 있는 칸은 항상 이미 채워져 있다고 가정할 수 있습니다. 따라서 각 칸을 채우는 방법은 모두 네 가지 입니다.

 

답의 수의 상한

이 문제의 답은 최대 얼마일까요? 우리의 알고리즘에서는 한 블록을 놓을 때마다 모두 네 가지의 선택지가 있는데, 우리는 최대 [50 / 3] = 16 개의 블록을 놓기 때문에 가능한 답의 상한은 4^16 = 2^32 개가 됩니다.

이것만 봐서는 도저히 시간 내에 모두 생성할 수 없을 것 같지만, 실제 입력을 손으로 풀어 보면 각 단계에서 우리가 선택할 수 있는 블록 배치가 크게 제한됨을 알 수 있습니다. 예를 들어 흰 칸이 6칸 있는 입력이 주어진다면, 이 이론상으로는 4^2 = 16가지의 방법이 있어야 하는데, 실제로는 잘 해봐야 두 가지 방법으로밖에 배치할 수 없지요. 흰 칸이 48개 있는 세 번째 예제 입력의 답이 1514 밖에 되지 않음을 보더라도 실제 답의 수는 이 상한보다 훨씬 작으리라고 예측할 수 있습니다. 프로그램을 실제 작성하고 손으로 작성한 여러 입력을 넣어 보면 시간 안에 답을 구할 수 있다는 확신을 얻을 수 있지요.

 

구현

다음 코드는 게임판 덮기 문제를 해결하는 재귀 호출 알고리즘을 보여줍니다. 다음 부분들을 주의해서 살펴보세요.

• 한 칸을 덮는 네 가지 방법을 각각의 코드로 구현하는 것이 아니라 coverType[] 배열에 저장했습니다. 이 배열은 네 가지 방법에서 새로 채워질 칸들의 상대 좌표의 목록을 저장합니다.
• set() 은 delta에 따라 블록을 놓는 역할과 치우는 역할을 같이 할 수 있습니다. 블록을 놓는 것과 치우는 것을 별도로 짤 필요가 없어지죠.
• set()은 해당 위치에 블록을 놓을 수 있는지 여부도 같이 판단합니다. 단 이때 곧장 함수를 종료하는 것이 아니라 마지막까지 함수를 실행한다는 데 유의할 필요가 있습니다. 만약 블록을 구성하는 세 칸 중에 한 칸에 표시를 한 뒤 두 번째 칸에 이미 블록이 놓여 있다는 것을 발견했다고 합니다. 이때 함수를 곧장 종료하면 나중에 덮었던 블록을 치울 때, 두 번째 칸에 이미 있던 블록마저 치워버리게 됩니다. 따라서 set() 은 그 자리에 그냥 1을 더함으로써 이칸에는 두 개의 블록이 겹쳐서 놓여 있다고 표시합니다.

// 주어진 칸을 덮을 수 있는 네 가지 방법
// 블록을 구성하는 세 칸의 상대적 위치 (drow, dcol)의 목록
const int coverType[4][3][2] = {
    { { 0, 0 }, { 1, 0 }, { 0, 1 } },  // (1)
    { { 0, 0 }, { 0, 1 }, { 1, 1 } },  // (2)
    { { 0, 0 }, { 1, 0 }, { 1, 1 } },  // (3)
    { { 0, 0 }, { 1, 0 }, { 1, -1 } }  // (4)
};

// board의 (row, col)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다.
// delta = 1 이면 덮고, -1이면 덮었던 블록을 없앤다.
// 만약 블록이 제대로 덮이지 않은 경우(게임판 밖으로 나가거나, 
// 겹치거나, 검은 칸을 덮을 때) false를 반환한다.
bool set(vector<vector<int> >& board, int row, int col, int type, int delta) {
    bool ok = true;
    for(int i = 0; i < 3; ++i) {
        const int nrow = row + coverType[type][i][0];
        const int ncol = col + coverType[type][i][1];
        if(nrow < 0 || nrow >= board.size() || ncol < 0 || ncol >= board[0].size())
            ok = false;
        else if(board[nrow][ncol] += delta) > 1)
            ok = false;
    }
    return ok;
}

// board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
// board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
// board[i][j] = 0 아직 덮이지 않은 칸
int cover(vertor<vector<int> >& board) {
    // 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
    int row = -1, col = -1;
    for(int i = 0; i < board.size(); i++) {
        for(int j = 0; j < board[i].size(); j++) {
            if(boardr[i][j] == 0) {
                row = i;
                col = j;
                break;
            }
        }
        if (row != -1) breakl;
    }
    // 기저 사례: 모든 칸을 채웠으면 1을 반환한다.
    if(row == -1) return 1;
    int ret = 0;
    for(int type = 0; type < 4; type++) {
        // 만약 board[row][col]를 type 형태로 덮을 수 있으면 재귀 호출한다.
        if(set(board, row, col, type, 1))
            ret += cover(board);
        // 덮었던 블록을 치운다.
        set(board row, col, type, -1);
    }
    return ret;
}

 

7. 최적화 문제

 

지금까지 다뤘던 문제와는 달리 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은 답'을 찾아 내는 문제들을 통칭해 최적화 문제(Optimization problem)라고 부릅니다. 예를 들어 n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수를 계산하는 것은 최적화 문제가 아닙니다. 우리가 원하는 답은 딱 하나밖에 없고, 더 좋은 답이나 덜 좋은 답이 없기 때문이죠. 반면 n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제, 아니면 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제 등은 최적화 문제가 됩니다. 사과를 골라내는 방법은 여러 가지인데, 이 중 특정 기준에의해 가장 좋은 답을 고르는 문제이기 때문입니다.

 

이 책에서는 최적화 문제를 해결하는 방법을 여러 가지 다루고 있는데, 그 중 가장 기초적인 것이 완전 탐색입니다. 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법입니다. 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문입니다.

예제: 여행하는 외판원 문제

가장 유명한 최적화 문제 중 하나로 여행하는 외판원 문제(Traveling Salesman Problem, TSP)가 있습니다. 어떤 나라에 n(2<=n<=10) 개의 큰 도시가 있다고 합시다. 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 합니다. 문제를 간단히 하기 위해, 각 도시들은 모두 직선 도로로 연결되어 있다고 합시다. 다음 그림은 한 도로망의 예를 보여줍니다. 이때 영업 사원이 여행해야 할 거리는 어느 순서로 각 도시들을 방문하느냐에 따라 달라집니다. 이때 가능한 모든 경로 중 가장 짧은 경로를 어떻게 찾아낼 수 있을까요?

 

 

무식하게 풀 수 있을까?

완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있을지 확인하는 것입니다. 우리는 시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 신경 쓰지 않고 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않습니다. 그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 되지요. n-1 개의 도시를 나열하는 방법은 모두 (n-1)! 가지가 있습니다. 도시가 열 개라면 경로의 수는 9! = 362,880 개가 됩니다. 물론 사람이 찾아보기에는 너무 큰 수입니다. 여전히 컴퓨터는 1초 안에 가볍게 처리할 수 있는 숫자입니다. 따라서 안전하게 완전 탐색을 사용해 문제를 해결할 수 있음을 알 수 있습니다.

 

재귀 호출을 통한 답안 생성

이 문제의 모든 답은 재귀 호출을 이용해 간단하게 만들 수 있습니다. n개의 도시로 구성된 경로를 n개의 조각으로 나눠, 앞에서부터 도시를 하나씩 추가해 경로를 만들어 가기로 하지요. 다음과 같은 형태의 함수를 작성해 이 문제를 해결할 수 있습니다.

 

shortestPath(path) = path 가 지금까지 만든 경로일 때, 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.

 

다음 코드는 이 아이디어를 직접적으로 구현합니다. 단, 원래 우리가 생각했던 함수 현태와는 달리 각 정점을 방문했는지를 나타내는 불린 값 배열 visited와 현재 경로의 길이 currentLength를 path와 함께 인자로 받고 있는 점을 유의해서 보세요.

int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열

// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
    // 기저 사례 : 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
    if(path.size() == n)
        return currentLength + dist[path[0]][path.back()];
    double ret = INF;  // 매우 큰 값으로 초기화
    // 다음 방문할 도시를 전부 시도해본다.
    for(int next = 0; next < n; next++) {
        if(visited[next]) continue;
        int here = path.back();
        path.push_back(next);
        visited[next] = true;
        // 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
        double cnad = shortestPath(path, visited, currentLength + dist[here][next]);
        ret = min(ret, cand);
        visited[next] = false;
        path.pop_back();
    }
    return ret;
}

 

8. 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

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

algospot.com :: CLOCKSYNC

 

9. 풀이: 시계 맞추기

 

이 문제를 있는 그대로 풀려고 하면 꽤나 복잡해집니다. 그러나 문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결할 수 있습니다.

이 문제에서 처음 깨달아야 할 것은 예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다는 것입니다. 두 스위치를 누르는 순서를 바꾼다고 해서 그 결과가 바뀌지 않기 때문입니다. 따라서 우리가 계산해야 할 것은 각 스위치를 몇 번이나 누를 것이냐 뿐입니다.

이렇게 문제를 바꾼다고 하더라도 완전 탐색을 곧장 적용할 수는 없습니다. 완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없고 따라서 그 조합의 수는 무한하기 때문입니다. 시계는 12시간이 지나면 다시 제 자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있습니다. 어떤 스위치를 네 번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하니 하나도 누르지 않은 것과 다름이 없습니다. 따라서 각 스위치를 누르는 횟수는 0에서 3 사이의 정수입니다. 열 개의 스위치가 있으니 전체 경우의 수는 4^10 = 1,048,576 개가 되지요. 구현에 따라 다르겠지만 일반적으로는 시간 안에 모든 경우를 세어 보기에 무리 없는 크기죠. 따라서 완전 탐색으로 무난하게 풀 수 있습니다.

완전 탐색 구현하기

아래 코드는 모든 경우를 세어 보는 재귀 호출 프로그램을 보여줍니다. 문제를 모두 열 조각으로 나눈 후 각 조각에서 한 스위치를 누를 횟수를 정하는 식으로 구현되었지요. 재귀 호출의 깊이가 정해져 있기 때문에 사실 이 코드는 10중 for문과 다르지 않지만 이 쪽이 훨씬 구현하기도 편하고 디버깅하기도 쉽습니다. 다음 부분을 유의해서 보세요.

 

• 만약 답을 구할 수 없을 경우 재귀 함수의 반환 값은 문제의 출력 값인 -1이 아니라 매우 큰 값이 됩니다. solve()는 재귀 호출하면서 가장 작은 출력 값을 찾게 되는데, -1 대신에 매우 큰 값을 반환하기로 약속하면 답이 없는 경우를 따로 확인하지 않아도 되니까요. 마지막에 답을 출력할 때 답이 매우 크다면 -1을 대신 출력해 주면 됩니다.
• 어떤 스위치가 어떤 시계에 연결되어 있는지를 2차원 배열을 통해 저장했습니다. 이때 i번째 스위치가 j번째 시계에 연결되어 있는지를 보려면 linked[i][j] 를 보면 됩니다. 이런 형태의 표현은 스위치마다 연결되어 있는 시계의 개수가 다르다는 점에 신경 쓸 필요가 없다는 장점이 있지만, 문제에 적혀있는 표현과 다르기 때문에 눈으로 확인하기가 약간 까다롭다는 단점도 있어요.

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
// linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
// linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS+1] = {
    // 0123456789012345
    "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..",
}

// 모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);
// switch번 스위치를 누른다.
void push(vector<int>& clocks, int switch) {
    for(int clock = 0; clock < CLOCKS; ++clock) {
        if(linked[switch][clock] == 'x') {
            clocks[clock] += 3;
            if(clocks[clock] == 15) clocks[clock] = 3;
        }
    }
}
// clocks: 현재 시계들의 상태
// switch: 이번에 누를 스위치 번호
// 가 주어질 때 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int switch) {
    if(switch == SWITCHES) return areAligned(clocks) ? 0 : INF;
    // 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
    int ret = INF;
    for(int cnt = 0; cnt < 4; cnt++) {
        ret = min(ret, cnt + solve(clocks, switch + 1));
        push(clocks, switch);
    }
    // push(clocks, switch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
    return ret;
}

 

10. 많이 등장하는 완전 탐색 유형

 

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열(permutation)이라고 부릅니다. 주어진 원소의 모든 순열을 생성해서 풀 수 있는 문제는 꽤 자주 만날 수 있습니다. 다른 문제의 부분 문제로 나타나기도 하는 만큼 모든 순열을 생성하는 코드를 한 번 신경써서 작성해 보면 좋습니다. 단, 가능한 순열의 수는 N!이 되는데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려우므로 완전 탐색 말고 다른 방법을 생각해야 합니다.

 

모든 조합 만들기

서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합(combination)이라고 부릅니다. 피자에 올릴 수 있는 다섯 종류의 토핑인 소시지, 쇠고기, 올리브, 피망, 양파 중 세 가지를 고르는 것이 조합의 좋은 예입니다.

 

2^n가지 경우의 수 만들기

n 개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 2^n가지 입니다. 이 모든 조합들을 생성하는 것은 굉장히 흔한 문제인데, 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있습니다.