[AlgoSpot][Python] 소풍

📒 문제 설명

🔖 https://www.algospot.com/judge/problem/read/PICNIC

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

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

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

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

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

---

✏️ 풀이 과정

📝 1차 시도

• 가능한 n의 최댓값이 10으로 크지 않고, 가능한 모든 조합의 개수를 구하는 문제이므로 완전 탐색으로 접근할 수 있다.

• 원소의 순서만 다른 순서쌍이나 조합을 중복해서 카운트하지 않도록 주의해야 한다. (우선 순위 필요)

• 우선 교재에서 소개한 대로 first_free 변수를 사용하여 짝이 지어지지 않은 학생 중에서 번호가 가장 작은 학생에 대하여 먼저 짝을 찾도록 했다.

• first_free가 -1인 경우, 짝이 지어지지 않은 학생이 없는 것이므로 1을 반환한다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def countingPairs(taken, are_friends):
	ans = 0
    first_free = taken.index(False) if False in taken else -1
    if first_free == -1: return 1

    for pair_with in range(first_free + 1, students_count):
        if (not taken[first_free] and not taken[pair_with] and are_friends[first_free][pair_with]):
            taken[first_free] = taken[pair_with] = True
            ans += countingPairs(taken, are_friends)
            # 백트래킹
            taken[first_free] = taken[pair_with] = False
    return ans

C = int(input())

for _ in range(C):
    students_count, friends_count = map(int, input().split())
    taken = [False] * students_count
    friends_list = list(map(int, input().split()))
    are_friends = [[False] * students_count for _ in range(students_count)]

    for i in range(0, friends_count * 2, 2):
        are_friends[friends_list[i]][friends_list[i + 1]] = True
        are_friends[friends_list[i + 1]][friends_list[i]] = True

    print(countingPairs(taken, are_friends))

---

📝 2차 시도

• 2차원 배열 are_freinds를 사용하지 않고 friends_list 배열을 그대로 사용하였으며, countingPairs 함수의 매개변수로 start를 사용했다.

• start 값이 증가함에 따라 백트래킹을 시행하므로 중복된 순서쌍이 카운트되지 않는다.

• 따라서 first_free 변수가 삭제되었고, taken이 모두 참일 때 1을 반환하도록 했다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def countingPairs(taken, start):
    ans = 0
    if all(t for t in taken): return 1

    for i in range(start, friends_count):
        idx1, idx2 = friends_list[i * 2], friends_list[i * 2 + 1]
        if not taken[idx1] and not taken[idx2]:
            taken[idx1] = taken[idx2] = True
            ans += countingPairs(taken, i + 1)
            taken[idx1] = taken[idx2] = False
    return ans

C = int(input())

for _ in range(C):
    students_count, friends_count = map(int, input().split())
    taken = [False] * students_count
    friends_list = list(map(int, input().split()))

    print(countingPairs(taken, 0))