피크닉

문제

algospot의 PICNIC 을 풀어보았습니다. PICNIC

Input 받기

각 케이스마다 문제를 한 번씩 실행하는 방식이 아니라 코드 실행 한 번에 여러 개의 케이스를 다 때려 박아야 하기 때문에 Input 받는 코드가 상당히 더럽습니다… 더 예쁜 방법이 있을 텐데… 저는 이렇게 했습니다.

cases = int(input()) # case 의 수
results = [0] * cases # 결과값을 저장하는 전역변수
friends_dicts = [] # 친구 쌍을 저장하는 dict 의 리스트
for _ in range(cases):
    friends_dicts.append({}) # 빈 dict 생성
students = [0] * cases # 각 케이스별 학생의 수

for cur_case in range(cases):
    students[cur_case], _  = [int(x) for x in input().split()]

    for i in range(students[cur_case]):
        friends_dicts[cur_case][i] = []

    friends = input().split()
    for i, x in enumerate(friends):
        if i % 2 == 0:
            a, b = int(friends[i]), int(friends[i+1])
            if a > b: # a와 b 중 작은 값이 key 가 되고, 큰 값이 value 가 됩니다.
                friends_dicts[cur_case][b].append(a)
            else:
                friends_dicts[cur_case][a].append(b)

리스트 results 를 생성할 때에는 results = [0] * cases 를 사용했지만 리스트 friends_dicts 를 생성할 때에는 friends_dicts = [{}] * cases 를 사용하지 않는 데에는 이유가 있습니다. 참고

결론만 얘기하자면 friends_dicts = [{}] * cases 를 사용하게 되면 리스트 안의 모든 dict 가 같은 인스턴스가 되어 버리기 때문입니다. (정보를 따로 저장할 수 없다는 이야기입니다.)

input 받는 부분은 따로 설명할 것은 없고, friends_dict 의 형성에 대해서 설명하겠습니다.

friends_dict 의 형성

for cur_case in range(cases):
    students[cur_case], _  = [int(x) for x in input().split()]

    for i in range(students[cur_case]):
        friends_dicts[cur_case][i] = []

    friends = input().split()
    for i, x in enumerate(friends):
        if i % 2 == 0:
            a, b = int(friends[i]), int(friends[i+1])
            if a > b: # a와 b 중 작은 값이 key 가 되고, 큰 값이 value 가 됩니다.
                friends_dicts[cur_case][b].append(a)
            else:
                friends_dicts[cur_case][a].append(b)

반 멤버가 0, 1, 2, 3 으로 총 4명이고, 모두가 친구라고 하면 결과값 dict 는 다음과 같은 모양입니다.

{
    0: [1, 2, 3],
    1: [2, 3],
    2: [3],
    3: [],
}

dict 의 의미는 다음과 같습니다.

0과 1, 2, 3 은 친구다.

1과 2, 3 은 친구다.

2과 3 은 친구다.

왜 작은 값이 key가 되고 큰 값이 value 가 되죠?
취향입니다, 뒤에 짝을 지어주는 함수 findCombination() 의 구현을 보게 되면 항상 아직 짝이 없는 친구중 0번째 친구를 짝 지어주기로 하는데, 구현이 이렇게 되면 작은 번호의 친구를 우선으로 dict에 적어주어야 하기 때문입니다. 반대로 아직 짝이 없는 친구중 마지막 번 친구를 먼저 짝 지어주기로 한다면 큰 값을 key로 해도 됩니다.

Insight: 친구사전과 친구 리스트의 차이

친구 여부를 저장하는 자료구조 후보로 2가지를 생각해 볼 수 있는데

• 친구사전 {0:[1,2,3] ...}
• 친구 튜플의 리스트 [(0,1), (0,2), (3,0) ...]

친구 사전의 형태를 취할 경우에 멤버 n 의 친구를 찾기 위해서 리스트 전체를 순회할 필요가 없습니다. 친구_사전[n] 으로 n의 친구들을 바로 알 수 있다는 장점이 있습니다.

그래서 친구 사전을 택했구요. 이제 친구사전을 이용해서 짝을 지어줘 봅시다.

짝짓기: findCombination()

def findCombination(left_behind):

    if len(left_behind) == 0: # 기저 사례 1: 모든 친구를 짝 지은 경우
        results[cur_case] += 1
        return

    # left_behind 중 0 번째 멤버를 짝 지어줄 방법을 찾는다.
    for elem in friends_dicts[cur_case][left_behind[0]]:
        if elem in left_behind:
            new_left_behind = left_behind[1:]
            new_left_behind.remove(elem)
            findCombination(new_left_behind)

함수 findCombination 에 들어가는 변수 left_behind 는 짝 없이 남겨진 친구들을 의미합니다. 맨 처음에 findCombination 을 실행할 때 left_behind 는 모든 친구들이 담겨진 리스트입니다.

실행 후, if 문을 건너서 for 문에 들어가게 되면, left_behind 에 남아있는 친구들 중 0번째 친구에게 짝을 지어주게 됩니다. 친구_사전[0] 으로 0의 친구들을 찾아주죠.

0번의 친구를 찾을 때 다음과 같은 경우의 수를 고려해 볼 수 있습니다.

• 0번은 외톨이: 0번은 친구가 없습니다. 이 경우 더 이상 재귀호출이 발생하지 않으므로 가능한 조합의 수는 0입니다.
• 0번은 친구가 한 명: for 문은 한 번 회전 하고 끝납니다.
• 0번은 친구가 많다: for 문이 여러번 회전 하는데, findCombination 을 호출할 때 주의할 점이 있습니다. 기존의 left_behind 를 수정하면 안됩니다. 항상 새로운 left_behind를 생성해서 넘겨주어야 한다는 것입니다. 0번과, 0번의 친구 A 를 짝 지어주었다면, left_behind 에서 0번과 A 를 제외한 새로운 new_left_behind 를 생성해서 findCombination()을 재귀호출 합니다. 만약 새로운 left_behind 를 생성하지 않고 기존 left_behind 에 손을 대었다면 for 문 실행 도중 left_behind 가 오염되게 되고, 다음 번 findCombination() 을 호출할 때 예상과 다른 답이 나오게 됩니다.

findCombination() 의 재귀 호출 중, left_behind 가 비게 되면 if 문을 통해 재귀호출이 종료됩니다. 출력할 결과에 +1 을 하고 return 합니다.

실행 예제

친구가 4명 (0, 1, 2, 3) 이고 모두가 서로 친구일 때 정답은 3 입니다.

• (01) (23)
• (02) (13)
• (03) (12)

프로그램은 다음의 순서대로 실행합니다.

full code

def findCombination(left_behind):

    if len(left_behind) == 0: # 기저 사례 1: 모든 친구를 짝 지은 경우
        results[cur_case] += 1
        return

    # left_behind 중 0 번째 멤버를 짝 지어줄 방법을 찾는다.
    for elem in friends_dicts[cur_case][left_behind[0]]:
        if elem in left_behind:
            new_left_behind = left_behind[1:]
            new_left_behind.remove(elem)
            findCombination(new_left_behind)


cases = int(input()) # case 의 수
results = [0] * cases # 결과값을 저장하는 전역변수
friends_dicts = [] # 친구 쌍을 저장하는 dict 의 리스트
for _ in range(cases):
    friends_dicts.append({}) # 빈 dict 생성
students = [0] * cases # 각 케이스별 학생의 수

for cur_case in range(cases):
    students[cur_case], _  = [int(x) for x in input().split()]

    for i in range(students[cur_case]):
        friends_dicts[cur_case][i] = [] # 모든 dict 가 한꺼번에 움직인다. 마치 같은 객체인것 처럼.

    friends = input().split()
    for i, x in enumerate(friends):
        if i % 2 == 0:
            a, b = int(friends[i]), int(friends[i+1])
            if a > b:
                friends_dicts[cur_case][b].append(a)
            else:
                friends_dicts[cur_case][a].append(b)


for cur_case in range(cases):
    findCombination(list(range(students[cur_case])))
    print(results[cur_case])