[알고스팟]PICNIC

문제

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

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

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

입력

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

출력

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

---

풀이

단순한줄 알았는데 생각보다 푸는데 애먹었던,,,

오답

단순히 순열 알고리즘으로 학생들의 순열을 다 찾은 후 둘 씩 묶어 조건에 맞는 경우만 정답에 넣는 방법을 시도 했으나 당연히 시간초과

• 예시입력
  n,m = 6 10
friend = 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
• [0,1,2,3,4,5]의 순열

  i	0	1	2	3	4	5
  perm[u]	0	1	2	3	4	5
  perm[v]	1	0	3	2	5	4

  다음과 같은 경우에
  - perm[u]에서 perm[u][0] = 0으로 자기 자신과 짝을 짓고 있으므로 count하지 않는다
  - perm[v]는 perm[v][0] = 1 , perm[v][1] = 0 처럼 친구 목록 조건에도 맞고 서로 짝 짓고 있으므로 조건에 맞는 경우이다.

• 시간 및 메모리 초과

그치만 경우의 수에서 착안한 방법인건 확실한듯 하여 더 고민해 보았다.

풀이

• student : 친구가 되는 쌍을 모두 튜플로 묶어 리스트로 만들어 둔다
• 조합 알고리즘에서 몇가지 조건을 추가하여 작성해 보았다.

  • tmp : 조합으로 만들어진 리스트

  • 친구 목록에서 한쌍의 친구를 꺼내 tmp에 있는 지 확인

    • 있는 경우 : tmp에 넣지 않고 바로 다음 친구쌍을 확인
    • 없는 경우 : tmp에 넣은 후 다음 친구 쌍을 확인하고 pop()으로 제거한 후 다시 다음 친구 쌍을 확인

  • tmp가 총 학생 수의 길이가 되면 answer에 해당 조합 리스트를 넣고 return

  • tmp가 완성되지 않더라도 index가 끝에 도달하면 return으로 base case를 만들어준다.

예시

n,m : 4,6
friend = [[0, 1], [1, 2], [2, 3], [3, 0], [0, 2], [1, 3]]

• [0,1]을 tmp에 넣는다.
• 다음 index인 [1,2]를 확인하고 조건에 맞지 않으므로 다음으로 넘어간다.
• [2,3]을 tmp에 넣는다. len(tmp)가 n이 되었으므로 해당 조합을 정답에 넣고 return한다.
• [2,3]을 pop() 한 후 더이상 맞는 조건의 쌍이 없으므로 [0,1]도 pop()을 하여 다음 index으로 넘어간다.

• 결과
  answer = [[0, 1, 2, 3], [1, 2, 3, 0], [0, 2, 1, 3]]

코드

import sys

testcase = int(sys.stdin.readline())

for t in range(testcase):
    c,n = map(int,sys.stdin.readline().split())
    friend = []
    student = list(map(int,sys.stdin.readline().split()))

    for i in range(n):
        friend.append([student[2*i],student[2*i+1]])
    
    answer = []
    def picnic(index,tmp):
        if(len(tmp)==c):
            temp = [i for i in tmp]
            answer.append(temp)
            return
        
        if index == n:
            return
        
        if friend[index][0] not in tmp and friend[index][1] not in tmp:
            tmp.append(friend[index][0])
            tmp.append(friend[index][1])
            picnic(index+1,tmp)
            tmp.pop()
            tmp.pop()
            picnic(index+1,tmp)
        else:
            picnic(index+1,tmp)
            
    
    picnic(0,[])
    
    print(len(answer))