알고스팟 : 소풍 (완전탐색, 조합)

 

 

 

 

 

탐색가능한 모든 조합의 수를 계산 하는 문제로 완전탐색 을 이용해서 문제를 해결할 수 있었다. 

여기서 중요한 것은 중복으로 계산되는 것을 제외하여야 한다는 것이다. 

즉 (1,0)과 (0, 1)은 서로 같은 사람끼리 짝을 이루었으므로 같은 경우라고 인지하여야 한다. 

이 부분을 해결하기 위해서 숫자 순서대로 먼저 오는 답 하나만 계산할 도록 first 인자를 이용해서 선택되지 않은 학생중에서 가장 번호가 빠른 학생의 짝을 찾도록 하였다. 

 

c = int(input())
def countPair():
    cnt = 0 
    first = -1
    for i in range(n):
        if not visited[i]:
            first = i 
            break
    if first == -1 :  return 1
    for i in range(first, n):
        if not visited[i] and isFriends[i][first]:
            visited[i] = visited[first] = True
            cnt += countPair()
            visited[i] = visited[first] = False
    return cnt 

for case in range(c) :
    n, m = map(int, input().split())
    isFriends = [[False]*n for _ in range(n)]  
    visited = [False]*n  
    pair = list(map(int, input().split()))
    for i in range(0, len(pair), 2):
        isFriends[pair[i]][pair[i+1]] = isFriends[pair[i+1]][pair[i]] = True
    print(countPair())