6.3 문제 : 소풍(Python)

문제 출처 : algospot.com :: PICNIC

algospot.com :: PICNIC

---

1. 해설 풀이 방법

def countParings(taken):
    firstFree = -1 # 남은 학생 중 가장 번호가 빠른 학생을 찾기위한 변수

    for i in range(n):
        if taken[i] == False:
            firstFree = i
            break

    # 기저 사례 : 모든 학생이 짝을 이루면 종료
    if firstFree == -1:
        return 1

    result = 0
    # 가장 번호가 빠른 학생의 짝을 매칭함
    for next in range(firstFree + 1, n):
        # 다음에 나오는 사람 중 친구 관계이면서 아직 짝을 이루지 못 했다면 짝으로 연결
        if not taken[next] and areFriends[firstFree][next]:
            taken[firstFree] = True
            taken[next] = True
            result += countParings(taken) # 재귀 호출로 결과 누적

            # 다른 짝이 생길 수 있는 경우를 계산하기 위해 짝 관계를 해제
            taken[firstFree] = False
            taken[next] = False

    return result


for tc in range(int(input())):
    n, m = map(int, input().split())
    
    taken = [False] * n # 현재 짝이 맺어져있는지 정보를 저장
    areFriends = [[False] * n for _ in range(n)] # 친구 관계를 저장
    for i in range(m):
        a, b = map(int, input().split())
        areFriends[a][b] = True
        areFriends[b][a] = True

    print(countParings(taken))
    

2. 해설

(1) 6.2 예제 : 보글 게임과 마찬가지로 재귀 호출을 통한 문제 해결 전략 사용

• 기저 사례는 1가지만 존재(모든 학생이 짝을 이루게 되면 종료)

(2) 현재 짝이 이뤄진 상태를 저장하는 리스트를 생성하여 정보를 저장할 필요가 있음

• 1차원 리스트 taken : 인덱스 i에 대해서 i번은 현재 짝이 있는지 없는지 Boolean 값을 통해 확인
• 2차원 리스트 areFriends : 문제에서 요구하는 친구 관계를 입력 후 저장

(3) 번호가 빠른 친구부터 순차적으로 짝을 맺고 다음 친구에 대해서 재귀적 방법을 통해 짝을 맺어주고 해제하는 방식을 반복하여 짝이 생길 수 있는 경우를 누적

 

3. 내가 문제를 해결하지 못한 이유 & 후기

  문제 해결에 대한 계획을 고안하지 못했다. 먼저 문제에 대한 정확한 이해를 하지 못했다. 직전의 보글 게임 문제와 마찬가지로 문제에 대한 정확한 이해를 하지 못했고, 그 다음 계획을 세우는 단계에서 해설에서 제시하는 1차원 리스트를 통해 현재 짝이 있는지 저장하는 방법을 생각하지 못했다. 그 결과, 문제에 손을 대지도 못하는 상황이 발생하였다.

  아직 문제들에 대해서 계획하는 능력이 떨어짐을 느낄 수 있었으며 이는 앞으로 여러 문제들을 접하다 보면 자연스럽게 해결 될 것으로 기대한다. 재귀 함수를 설계(?)하는 방법 역시 마찬가지이다. 그렇기 위해서 꾸준히 많은 문제들을 접하고 해석하는 과정을 반복할 예정이다. 또한, 시간 제한에 구애받지 않고 깊고 다양하게 생각하는 습관을 만들어야 겠다는 생각을 하게 되었다.

---

github : Algorithmic_Problem_Soving_Strategies/q1_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies