알고스팟 문제 풀이 PICNIC

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "PICNIC"에 대한 풀이입니다.

 

목차

1. 문제 해결 전략
2. 코드 전문

문제 해결 전략

 

PICNIC 문제 URL은 다음과 같습니다. 급하신 분들은 바로, 코드 전문으로 넘어가주세요!

 

• PICNIC URL

 

제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 먼저 이해를 위해서 3번째 입력에 대해서, 살펴보도록 하겠습니다.

 

n = 6, m = 10
set = (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)

 

이것을 그림으로 나타내 봅시다.

먼저 (0, 1) 세트를 골랐을 때, 다음으로 고를 수 있는 친구의 셋은 (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) 입니다.

그 다음으로 (2, 3)을 고르면, (4, 5) 세트를 고를 수 있기 때문에, 모든 학생들을 친구와 짝을 맺게 해줄 수 있습니다.

만약 (2, 3)을 고르지 않았을 땐 (2, 4)를 고를 수 있습니다. 역시 (3, 5)를 고를 수 있기 때문에, 짝을 지어줄 수 있습니다.

근데, 세트 (2, 3), (2, 4)을 고르지 않았다고 가정해봅시다. (3, 4)를 고르게 되면, 2번과 5번은 친구가 아니기 때문에, 짝을 다 지어줄 수 없습니다.

(3, 5), (4, 5)는 각각 (2, 3), (2, 4)를 골랐을 때와 같은 상황이므로, 같은 경우의 수라고 생각하시면 됩니다. 위 과정을 (0, 1) 세트를 골르지 않았을 때로 반복해서 친구끼리 짝을 지은 전체 경우의 수를 반환하면 됩니다.

 

결국 이 문제를 해결하기 위해서는 세트 목록 중에서 한 세트에 대해서 선택한 것과 안 선택한 것의 경우의 수를 따져보면 됩니다.

 

또한, 이 문제를 풀 때는 반복문 보다는 재귀 호출문이 조금 더 편하다고 생각합니다. 왜냐하면, 반복문이라고 생각해봅시다. 이 때, 선택을 했을 경우의 수와 선택을 안했을 때 경우의 수를 쉽사리 생각할 수 있나요? 저의 경우, 반복문으로 해결하는게 쉽게 생각이 나지 않았습니다.

 

반면, 재귀 호출 방식을 선택했을 때는, 해당 인덱스에서 선택하느냐 안하느냐로 코드로 쉽게 나타낼 수 있기 때문에, 이 방법이 조금 더 좋다고 생각합니다. 다음 코드처럼 말이죠.

 

int solve(int m, int idx, vector<bool> isCheck, const vector< vector<int>>& friendSet) {
    // 재귀 탈출 조건1: 모든 짝이 지어진 경우 1을 추가합니다.
    if (IsAllCheck(isCheck)) {
        return 1;
    }

    // 재귀 탈출 조건2: 친구 목록을 다 순회해도, 짝이 지어지지 않은 경우입니다.
    if (m <= idx) {
        return 0;
    }

    int ret = 0;
    auto pair = friendSet[idx];
    
    // 친구 set을 선택하지 않았을 때 경우의 수입니다.
    ret += solve(m, idx + 1, isCheck, friendSet);

    // 만약 이 친구 set의 인원 중 누구라도 이전에 선택됐다면, 이 set은 선택 될 수 없습니다.
    // 따라서, 선택하지 않았을 때의 경우의 수만을 반환합니다.
    if (isCheck[pair[0]] || isCheck[pair[1]]) {
        return ret;
    }

    // 친구 set을 선택했을 경우입니다.
    isCheck[pair[0]] = true;
    isCheck[pair[1]] = true;
    ret += solve(m, idx + 1, isCheck, friendSet);

    // 친구 set을 선택했을 때와 안 선택했을 때의 경우의 수를 합한 값을 반환합니다.
    return ret;
}

 

주석을 살펴보시면, 무엇을 말하고 있는지 금방 아실 수 있을 겁니다.

코드 전문

다음은 알고리즘 풀이 코드 전문입니다.  main은 입력에 대해서 예외 처리를 한 후 solution 함수를 부릅니다. solution 함수는 입력 n에 대해서, 체크 여부를 나타내는 리스트를 만들고, 그것을 가지고 solve 함수를 호출한 그 결과를 반환합니다.

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 10;
const int MAX_M = MAX_N * (MAX_N-1) / 2;

bool IsAllCheck(const vector<bool> &isCheck) {
    for (int i=0; i<isCheck.size(); i++) {
        if (!isCheck[i]) {
            return false;
        }
    }

    return true;
}

int solve(int m, int idx, vector<bool> isCheck, const vector< vector<int>>& friendSet) {
    if (IsAllCheck(isCheck)) {
        return 1;
    }

    if (m <= idx) {
        return 0;
    }

    int ret = 0;
    auto pair = friendSet[idx];
    ret += solve(m, idx + 1, isCheck, friendSet);

    if (isCheck[pair[0]] || isCheck[pair[1]]) {
        return ret;
    }

    isCheck[pair[0]] = true;
    isCheck[pair[1]] = true;
    ret += solve(m, idx + 1, isCheck, friendSet);
    return ret;
}

int solution(int n, int m, vector< vector<int>> friendSet) {
    auto isCheck = vector<bool>(n, false);
    return solve(m, 0, isCheck, friendSet);
}

int main() {
    int c;
    cin >> c;

    if ( !(0 < c && c <= 50) ) {
        cout << "fail" << endl;
        return 0;
    }

    for (int i=0; i<c; i++) {
        int n, m;
        cin >> n >> m;

        if ( !(2 <= n && n <= MAX_N) ) {
            cout << "fail" << endl;
            return 0;
        }

        if ( !(0 <= m && m <= MAX_M) ) {
            cout << "fail" << endl;
            return 0;
        }

        vector< vector<int>> friendSet;

        for (int j=0; j<m; j++) {
            int a, b;
            cin >> a >> b;
            friendSet.push_back({a, b});
        }

        int result = solution(n, m, friendSet);
        cout << result << endl;
    }

    return 0;
}

 

다음 코드를 제출하면, 40ms 이내로 무난하게 통과하는 것을 확인할 수 있습니다. 근데 0ms로 통과하는 사람들이 있는 것을 보면 "동적 계획법"이나 다른 알고리즘 패러다임을 이용하여 최적화하는 방식이 있을 것으로 추정됩니다. 이는 솔루션을 찾게 되면, 그 때 재 업로드 하도록 하겠습니다.