소풍(PICNIC)

문제

문제 내용은 아래 링크 참조
https://www.algospot.com/judge/problem/read/PICNIC

풀이

시간 제한: 1s
메모리 제한: 64MB

테스트 케이스 tc (tc <= 50)
학생의 수 n (2 <= n <= 10)
친구 쌍의 수 m (0 <= m <= n(n-1)/2)

최대 10명의 학생이 모두 친구인 경우라고 해도 2명씩 짝지어 주는 경우의 수는

$\dfrac{\binom{10}{2} * \binom{8}{2} * \binom{6}{2} * \binom{4}{2} * \binom{2}{2}} {5!} = 30240$

으로 경우의 수가 작음을 알 수 있다.

그래서 brute-force로 방향을 잡고 문제를 풀었다

소스 코드

#include <bits/stdc++.h>
using namespace std;

// variable
int tc;
int n, m;
bool selected[10];
bool areFriends[10][10];

int countPairings(int one = 0) {
  while (one < n && selected[one])
    one++;
  
  if (one == n) 
    return 1;
  
  int ret = 0;
  for (int other = one + 1; other < n; ++other) {
    if (selected[other] || !areFriends[one][other]) 
      continue;
    
    selected[one] = selected[other] = true;
    ret += countPairings(one + 1);
    selected[one] = selected[other] = false;
  }
  
  return ret;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> tc;
  
  while (tc--) {
    cin >> n >> m;
    
    memset(selected, false, sizeof(selected));
    memset(areFriends, false, sizeof(areFriends));
    
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      areFriends[a][b] = areFriends[b][a] = true;
    }
    
    cout << countPairings() << '\n';
  }
}

후기?

사실 위의 코드는 내가 짠 코드 + 알고리즘 문제 해결 전략(종만북)의 코드를 개인적으로 마음에 드는 부분들을 합친 코드다.

특히 변수, 함수명이라던가 좋은 잡기술? 같은 건 무조건 내 코드에 반영시키려고 노력했다.

코드를 조금 더 일관성 있게 읽기 쉽게 짜려고 시도하고 있는데 이 시리즈가 올라가는 동안에도 코드 스타일이 조금씩 변할 것 같다.