[알고리즘 문제해결 전략]6장. 무식하게 풀기_③

PICNIC in algospot

---

problem

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • PICNIC
  • 1000ms
  • 65536kb
  • 9666
  • 4136 (42%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카) (써니,티파니) (효연,유리)
• (태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

예제 입력

3 
2 1 
0 1 
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

예제 출력

1
3
4

Tinking

우선, 완전탐색을 목표로 예상 최대시간을 계산해 보자. 총 학생의 수는 최대 10명이다. 그러면 모든 경우의 수를 고려해보는 경우의 수는 아래와 동일 하다.

(10 C 2) * (8 C 2) * (6 C 2) * (4 C 2) * (2 C 2) = 113400

 즉 컴퓨터의 시간으로는 해결가능한 문제이다. 하지만, 중복의 문제가 발생한다. 이는 4명의 친구들을 예로 생각해보자.

학생 1 2 3 4

가능한 쌍 (정답) 

 (1, 2) (3, 4)

 (1, 3) (2, 4)

 (1, 4) (2, 3)

위의 아이디어로 나올 수 있는 경우의 수

(1, 2) (3, 4)

(1, 3) (2, 4)

(1, 4) (2, 3)

(2, 3) (4, 1)

(2, 4) (3, 1)

(3, 4) (2, 1)

하지만 , 4C2 * 2C2를 계산해보면 6 즉, 중복이 발생한다. 이를 해결하기 위해 다른 방법을 모색해보자. 

학생 1, 2, 3, 4를 정렬한 후, 무조건 본인의 뒤에 있는 학생을 선택해서 경우의 수를 구해보자.

(1, 2) (3, 4)

(1, 3) (2, 4)

(1, 4) (2, 3)

자, 그러면 학생 6명에 대해서도 생각해보자

학생 1,2,3,4,5,6

경우의 수

(1, 2) (3, 4) (5, 6)

(1, 2) (3, 5) (4, 6)

(1, 2) (3, 6) (4, 5)

(1, 3) (2, 4) (5, 6)

(1, 3) (2, 5) (4, 6)

(1, 3) (2, 6) (4, 5)

(1, 4) (2, 3) (5, 6)

(1, 4) (2, 5) (3, 6)

(1, 4) (2, 6) (3, 5)

(1, 5) (2, 3) (4, 6)

(1, 5) (2, 4) (3, 6)

(1, 5) (2, 6) (3, 4)

(1, 6) (2, 3) (4, 5)

(1, 6) (2, 4) (3, 5)

(1, 6) (2, 5) (3, 4)

총 15가지의 경우 즉, 6 C 2 * 4 C 2* 2 C 2 * 1/3! = 15 가 맞다.

자, 그렇다면 해당 경우만 우선 구현을 해보자.

int ans = 0;
int friends[N][N] //친구 여부 확인
int selected[N] // 선택된 친구인지 아닌지
void solve() {
    int first_sel = -1;
    for (int i = 0; i < N; i++) {//숫자들 중 선택되지 않은 가장 작은 번호의 친구를 고른다.
        if (selected[i] == 0) {
            first_sel = i;
            break;
        }
    }
    if (first_sel == -1) {//모든 친구들의 짝이 있을 경우 하나의 답이 만들어 진것이므로 ans++를 해준다.
        ans++;
        return;
    }
    for (int pair = first_sel + 1; pair < N; pair++) {// first_sel의 번호보다 큰 번호의 친구를 탐색한다.
        if ((selected[pair] == 0) && (friends[pair][first_sel] == 1)) {//친구가 선택되지 않았고 first_sel의 친구와 해당 친구가 서로 친구인 경우 짝을 이루게 한다.
            selected[pair] = selected[first_sel] = 1;
            solve();//다음의 짝을 찾지못한 친구를 찾기위해 다시 함수를 부른다.
            selected[pair] = selected[first_sel] = 0;
        }
    }
}

[코드 1 PICNIC 핵심 코드]

Solve

success

출처

---

문제:  algosport PICNIC문제( 링크 )