[알고리즘] 소풍

# 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드

from sys import stdin
import sys

sys.stdin = open('1.txt')
# 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

def countPairings(taken, areFriend, n):
    finished = True
    for i in range(n):
        if not taken[i]: finished = False
    if finished: return 1
    ret = 0
    for i in range(n):
        for j in range(n):
            if not taken[i] and not taken[j] and areFriend[i][j]:
                taken[i] = taken[j] = True
                ret += countPairings(taken,areFriend,n)
                taken[i] = taken[j] = False
    return ret


TC = int(input())
for tc in range(TC):
    n, m = map(int, input().split())
    list = input()
    list = list.split(' ')
    areFriend = [[False] * 10 for _ in range(10)]
    taken = [False] * 10
    for li in range(0, len(list), 2):
        a = int(list[li])
        b = int(list[li + 1])
        areFriend[a][b] = areFriend[b][a] = True
    print(countPairings(taken, areFriend, n))

 

중복된 경우의 수가 많다. 이를 처리해주는 새로운 알고리즘을 짜보자

from sys import stdin
import sys

sys.stdin = open('1.txt')
# 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

# 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드

def countPairings(taken, areFriend, n):
    finished = True
    for i in range(n):
        if not taken[i] : finished = False
    if finished: return 1
    ret = 0
    for i in range(n):
        for j in range(n):
            if not taken[i] and not taken[j] and areFriend[i][j]:
                taken[i] = taken[j] = True
                ret += countPairings(taken,areFriend,n)
                taken[i] = taken[j] = False
    return ret

# 6.5 소풍 문제를 해결하는 재귀 호출 코드

def countPairings2(taken, areFriend, n):
    firstFree = -1
    for i in range(n):
        if not taken[i] : firstFree=i
    # 기저사례 : 모든 taken이 다 True 인 경우 한가지 경우가 만들어지므로 1 반환
    if firstFree==-1: return 1
    ret = 0
    for pairWith in range(n):
        if not taken[pairWith] and areFriend[firstFree][pairWith]:
            taken[firstFree] = taken[pairWith] = True
            ret += countPairings2(taken,areFriend,n)
            taken[firstFree] = taken[pairWith] = False
    return ret

TC = int(input())
for tc in range(TC):
    n, m = map(int, input().split())
    list = input()
    list = list.split(' ')
    areFriend = [[False] * 10 for _ in range(10)]
    taken = [False] * 10
    for li in range(0, len(list), 2):
        a = int(list[li])
        b = int(list[li + 1])
        areFriend[a][b] = areFriend[b][a] = True
    # print(countPairings(taken, areFriend, n))
    print(countPairings2(taken, areFriend, n))