Welcome to My IT World

[재귀 관련 참고사항]

모든 재귀함수는 ‘더 이상 쪼개지지 않는’ 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문 포함필요(기저 사례 base case)

기저사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해서 계산될 수 있도록 신경써야 함

또한, 입력이 잘못되거나 범위에서 벗어난 경우도 기저사례로 택해서 맨 처음 처리하면 함수 호출 시점에 이런 오류를 검사할 필요가 없음

⇒ 재귀함수는 보통 한군데 이상에서 호출되기 때문에 이 습관은 반복적 코드 제거에 큰 도움이 됨

문제

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

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

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

입력

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

출력

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

예제 입력

3 2 1 0 1 4 6 0 1 1 2 2 3 3 0 0 2 1 3 6 10 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

예제 출력

1 3 4

출처 : https://www.algospot.com/judge/problem/read/PICNIC

[접근법]

1. 완전탐색으로 풀 수 있을까? ⇒ 현 문제 상의 데이터크기라면 가능
2. 조합으로 다 뽑아서 검사할까? ⇒ 너무 무식해서 하고싶지 않음
3. 문제의 단순화/순서강제 ⇒ 순서대로 뽑는 걸로 강제하면 선택지가 줄어듬
4. 짝들은 그래프로 데이터 전처리하고 dfs로 접근
5. 모두 짝을 이뤘는지는 visited(set)의 length로 체크

[주의사항]

visited를 넘겨줄 때, deepcopy로 새 visited만들어서(new_visited) 넘겨줘야함

그렇지 않으면 그 전 방문기록이 쌓여서 결과값에 오류 발생

[기타 refactoring]

deepcopy로 visited를 다 복사하지 말고 책의 풀이처럼, visited처리 후 dfs 넘긴다음에 unvisited하는 것이 더 효율적일 수도 있을듯

[내가 푼 코드]

from collections import defaultdict
from copy import deepcopy

#데이터 전처리
graph = defaultdict(list)
for pair in friends:
    student1, student2 = pair
    graph[student1].append(student2)
    graph[student2].append(student1)

answer = 0
visited = set()

#dfs
def dfs(visited, graph, n):
    global answer
    if len(visited) == n:
        answer += 1
        return
    for i in range(n):
        if i not in visited:
            visited.add(i)
            for friend in graph[i]:
                if friend not in visited:
                    new_visited = deepcopy(visited)
                    new_visited.add(friend)
                    dfs(new_visited, graph, n)
            break
    return

dfs(visited, graph, n)
print(answer)

[책에 나온 스타일대로 풀어본 코드]

visited를 True/False를 가진 배열(taken)로 처리함

해당 값들을 넘겨주고 visited 정보를 다시 초기화하기 위한 작업들을 눈여겨 볼 것(다시 False 처리해줌)

def are_friends(i, j, graph):
    if j in graph[i]: return True
    return False

def is_finished(taken):
    for i in range(n):
        if taken[i] != True:
            return False
    return True

taken = [False]*n

def count_pairs(graph, taken, n):
    if is_finished(taken): return 1
    ret = 0
    target = -1
    for i in range(n):
        if taken[i] == False:
            target = i
            break
    for j in range(n):
        if taken[j] == False and are_friends(target, j, graph):
            taken[target] = True
            taken[j] = True
            ret += count_pairs(graph, taken, n)
            taken[target] = False
            taken[j] = False
    return ret

print(count_pairs(graph, taken, n))