[ALGOSPOT] PICNIC (소풍)

🎯 ALGOSPOT - PICNIC (소풍)

🤔 나의 풀이

📌 문제

- ALGOSPOT > PICNIC

📌 날짜

2020.03.16

📌 시도 횟수

Failed

💡 Code

from collections import defaultdict

# 친구 쌍을 양방향 그래프(dict)로 나타내기
def match(pairs):
    pdict = defaultdict(list)
    for i in range(0, len(pairs), 2):
        pdict[pairs[i]].append(pairs[i + 1])
        pdict[pairs[i + 1]].append(pairs[i])
    return pdict
 
 
def solution(num, pairs):
    # 가능한 친구 쌍을 구해서 모든 케이스를 result에 저장하기
    def match_students(cur, left, matched):
        if left == 0:
            result.append(matched)
            return
 
        for i in range(cur, num):
            for j in range(i + 1, num):
                if (j in pdict[i] and i in pdict[j] and i not in matched and j not in matched):
                    match_students(i + 1, left - 2, matched + [i, j])
 
    pdict = match(pairs)
    match_students(0, num, [])
 
 
# 입력 & 실행
for _ in range(int(input())):
    N, M = map(int, input().split())
    pairs = list(map(int, input().split()))
    result = []
    solution(N, pairs)
    print(len(result))

❌ (한번에 맞추지 못한 경우) 오답의 원인

문제점 1. 그래프가 하나로 이어지지 않은 경우를 탐색하지 못함
- 친구 관계를 그래프로 표현 했을 때 그래프가 하나로 이어져 있지 않은 경우를 체크하지 못함
ex. 친구 관계가 서로 "[1, 2], [3, 4, 5, 6]"인 경우 그래프로 나타내면 2개로 나뉘기 때문에
이를 제대로 처리하지 못함

문제점 2. 중복을 제거하지 못함 (중복되는 경우를 제거하지 못해 시간초과가 뜸)
- [1, 2, 3, 4]와 [1, 2, 4, 3]과 [2, 1, 3, 4]과 [2, 1, 4, 3]은 같은 결과인데
이를 코드 내에서 잡아내지 못해서 시간 초과가 떴다.

- 나는 그래프 바보ㅠㅠ´¯`(>▂<)´¯`·.  더 열심히 풀어야겠다. 여전히 재귀가 너무 헷갈린다.

💡 문제 해결 방법(위의 오답의 원인들을 각각 어떻게 해결할까?)

Q1. 어떻게 그래프가 하나로 이어져 있지 않아도 모든 케이스를 돌 수 있을까?
- 그냥 모든 그래프 key값에 대해서 시작하여 순회해보면 된다!
- for i in range(cur, num) << 이 코드가 바로 그래프의 모든 key를 시작점으로
설정해서 순회해보는 코드이다.


Q2. 어떻게 중복을 없앨 수 있을까?
⭐해결 방법 : "한 쌍의 친구 관계 내"에서는 "무조건 순서가 오름차순"이 되도록 한다⭐
- 이렇게 해결하게 되면 [1, 2, 3, 4], [1, 3, 2, 4], [1, 4, 2, 3]같은 케이스만
출력할 수 있게 되므로 중복 문제를 해결할 수 있게 된다!

💡 새롭게 알게 된 점

- '순서'가 그래프 내의 중복을 해결할 수 있는 해결책이라는 점을 기억하자!