[ALGOSPOT] 알고스팟 PICNIC 소풍(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 PICNIC 소풍

(Python)

(글쓴날 : 2020.05.12)

 

---

* ALGOSPOT, 알고스팟 PICNIC 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 PICNIC 소풍

---

1) 문제

문제 링크 : https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

---

2) 풀이 과정

* 시간 복잡도 : O(n!)

 

최대 10명의 학생들이 주어지고, 학생들 사이의 친구 관계가 쌍으로 주어질 때, 모든 학생들을 친구끼리 짝이 되도록 하는 경우의 수를 구하는 문제입니다.

 

저의 경우, DFS를 적용하였으며, Python을 사용했습니다.

먼저, 친구 관계를 표시하는 인접 행렬을 구현한 후, 완전 탐색을 실시하여 친구끼리 짝을 맺었을 때, 남아있는 학생이 없다면 답을 1 증가시키는 식으로 문제를 해결했습니다.

단, 짝이 맞아떨어진 학생들이 순서만 바뀐 채 중복될 경우 답을 여러 번 증가시키게 되므로, 반복 제어 변수를 DFS() 함수의 인자로 넘겨 순열이 아닌 조합을 구했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def DFS(startI, remainingFriend):
    if not remainingFriend:
        return 1
 
    possibleCase = 0
 
    for i in range(startI, n):
        if not visit[i]:
            for j in range(i + 1, n):
                if not visit[j] and isFriend[i][j]:
                    visit[i] = visit[j] = True
                    possibleCase += DFS(i, remainingFriend - 2)
                    visit[i] = visit[j] = False
    
    return possibleCase
 
 
C = int(input())
 
for _ in range(C):
    n, m = map(int, input().split())
    visit = [False] * n
    isFriend = [[False] * n for _ in range(n)]
    friendsList = list(map(int, input().split()))
 
    for i in range(0, len(friendsList), 2):
        isFriend[friendsList[i]][friendsList[i + 1]] = True
        isFriend[friendsList[i + 1]][friendsList[i]] = True
 
    print(DFS(0, n))

---