150416 짝짓기

수학문제를 풀다가 이런 문제를 본적이 있을 것이다.

4명을 두명씩 짝지으려고 한다 그런데 서로 친한친구가 아니면 짝지어서 다니지 않기 때문에 친한친구끼리 짝을 지어주려고 한다 이때 짝을 짓는 경우의 수는 ?

이걸 코드로 구현한다면 어떻게 구현해야 할까?

완전탐색을 이용하면 가볍게 풀 수 있다.

일단 학생 수 * 학생 수 만큼 배열을 만들어서 0과 1이 친구라면 [0][1]에 True를 넣는다 물론 [1][0]도 True가 된다.

그리고 짝을 표시하는 배열을 학생수만큼 만들고 짝이 없는 두 친구를 골라 짝이 될 수 있다면 그 자리에 True를 채워넣는다 그리고 모두 짝이 되면 종료하도록 한다. 그 후 돌아와서 다시 False로 넣는다 ( 이미 이 둘이 짝이 되는 모든 경우의 수를 훑어봤기 때문에 )

그렇게 제귀함수를 돌다보면 모든 경우의 수를 셀 수 있다.

코드를 확인해 보자

def main(): case = input() for loop in xrange(case): n, m = map(int, raw_input().split()) pair = map(int, raw_input().split()) # 짝을 나눈다 pair = [(pair[i], pair[i+1]) for i in xrange(0, m*2, 2)] # 친구인지 아닌지 판별하여 True와 False를 넣는다. are_friend = [[True if (i, j) in pair or (j, i) in pair else False for j in xrange(n)] for i in xrange(n)] # 짝인지 아닌지 판별하는 배열 taken = [False for _ in xrange(n)] print count_pairings(taken, n, are_friend) def count_pairings(taken, n, are_friend): free = -1 # 가장 작은 숫자부터 짝을 채워나가도록 한다 ( 중복을 막기 위해 ) for i, is_pair in enumerate(taken): if not is_pair: free = i break # 모두 짝이 있다면 1을 반환한다. if free is -1: return 1 ret = 0 for i in xrange(free+1, n): # 둘다 짝이 없고 둘이 짝이 될 수 있을 때 if not taken[free] and not taken[i] and are_friend[free][i]: taken[i] = taken[free] = True # 재귀함수를 호출해서 짝이 될 수 있는 경우에 + 가 된다. ret += count_pairings(taken, n, are_friend) # 재귀 함수를 통해 모든 짝을 훑어 봤기 때문에 다시 False 로 바꾼다 taken[i] = taken[free] = False return ret