[종만북] - 소풍(완전탐색)

해결과정 

완전탐색할 때 가장 주의해야할 점은 중복으로 세는 문제이다.

 

아래 예시는 중복으로 세고 있는 경우이다.

int n;
bool areFriends[10][10];
//taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int coutPairings(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;
}

여기에는 두 가지 문제점이 있다.

 

1. 같은 학생들을 두 번 짝지어 준다. 예를 들어 (0,1)과 (1,0)을 따로 세고 있다. (순열)

2. 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다. 예를 들어 (0,1)후에 (2,3)을 짝 지어 주는 것과 (2,3)후에 (0,1)을 짝지어주는 것은 같은 방법인데 다른 경우로 세고 있다.

 

간단히 말하면, 조합을 구해야하는데, 순열을 구한 것이다.

 

이를 해결하기 위해서, 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다.

흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있다.

예를 들어, (2,3), (0,1)이나 (1,0) (2,3)은 세지 않고, (0,1) (2,3)만 세는 것이다.

 

이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.

 

아래는 중복을 해결한 코드이다.

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;
}