[python] algospot picnic 문제풀이

문제

학생들을 두 명씩 짝을 지으려 한다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 한다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하여라.

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

algospot.com :: PICNIC

 

문제풀이

이 문제는 현재 x명의 짝을 짓는 문제에서 (a,b)로 한 쌍의 짝을 만들고, x-2명의 짝을 짓는 부분 문제로 찢어진다.

부분 문제의 개수는 현재 짝을 만드려는 a의 친구 수와 같다.

문제에서 학생의 수는 최대 10명이고 친구 쌍의 수는 최대 45라고 한다. 그러면 재귀로 구현했을 때 

재귀의 최대 깊이는 5가 된다. 10명 -> 8명 -> 6명 -> 4명 -> 2명으로 줄어들기 때문이다.

부분 문제의 최대 개수는 9개가 된다. 1명이 가질 수 있는 친구의 최대 수는 9이기 때문이다.

문제의 시간복잡도는 O(9^5)로 제한 시간 안에 해결할 수 있다.

 

주의해야 할 점은 (a,b), (c,d)와 (c,d), (a,b)로 짝지어지는 방법은 같은 방법으로 봐야 한다.

이러한 중복을 해결하기 위해 순서를 강제하는 방법이 있다. 무조건 사전 순서로 앞에 있는 문자를 먼저 처리하는 것이다.

즉, (a,b)와 (c,d)에서 a가 c보다 사전 순으로 앞에 있는 문자니까 무조건 (a,b)를 먼저 처리하게 되고,

(c,d)를 먼저 처리하는 경우는 없어지게 되어 중복은 사라진다.

방법의 수를 셀 때 순서의 차이는 고려하지 않기 때문에 순서를 강제해도 결과는 달라지지 않는다.

 

문제를 풀기 위해  pairing 함수를 구현했다.

- pairing(finished) : finished라는 모든 학생들의 짝지어진 여부를 담고 있는 리스트를 입력으로 받는다. 거기서 짝지어지지 않은 첫 번째 학생 A의 인덱스를 찾고, 그 인덱스로부터 뒤에 있는 인덱스를 반복문을 통해 돌며 A와 친구이며 아직 짝지어지지 않은 학생을 발견하면 두 학생을 짝지어주고 자기 자신을 호출해 반복한다. 모든 학생이 짝지어지면 재귀를 종료한다.

코드

N = int(input())


def pairing( finished ) :

    if all(finished) :
        return 1

    first_people = finished.index(False)
    count = 0

    for i in range(first_people+1, len(finished)) :

        if not finished[i] and areFriend[first_people][i] :

            finished[i] = True
            finished[first_people] = True
            count += pairing(finished)
            finished[i] = False
            finished[first_people] = False

    return count


for _ in range(N) :

    n,m = map(int, input().split())
    pairs = []
    line = list(map(int,input().split()))

    for i in range(0,m*2,2) :
        pairs.append(line[i:i+2])

    areFriend = [ [ False for _ in range(n)] for _ in range(n) ]

    for pair in pairs :
        areFriend[pair[0]][pair[1]] = True
        areFriend[pair[1]][pair[0]] = True

    finished = [False for _ in range(n)]

    print(pairing(finished))



# 짝을 만드는 경우의 수를 세는 문제이다. 학생의 수가 10 이하이기 떄문에 완전 탐색으로도 해결 가능하다.
# 처음에는 친구를 의미하는 리스트를 이용하여 완전탐색을 하려고 했지만 최대값이 45로 시간초과가 난다.

# 문제를 자세히 살펴보면 n명의 짝을 짓는 문제이다. 이 문제는 n-2명의 짝을 짓는 문제인 subproblem으로 쪼개질 수 있다.

# (1,4) (3,2) 와 (3,2) (1,4)가 중복되어 나오는 것을 막기 위해서 순서를 강제할 필요가 있다.
# 여기서는 작은 수를 먼저 짝을 맺는 방식을 사용해 중복을 없앴다.

 

초기 접근 방식과 오답의 원인

처음 문제를 접했을 때 친구 여부의 리스트를 이용해 재귀를 돌리려고 했다.

재귀의 입력으로 이때까지 완성된 짝을 담고 있는 리스트를 주고, 짝이 n/2가 될 때까지 반복하려고 했다.

그렇게 하다 보니 입력값의 개수도 많아지고, 다양한 처리를 해야 하는 등 문제가 복잡해져서 포기했다.

재귀의 기준을 어떤 거로 잡느냐에 따라 문제가 더욱 복잡해지기도 한다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.