[Python/파이썬] 백준 15270번 친구 팰린드롬

https://www.acmicpc.net/problem/15270

 

코드

n, m = map(int, input().split())
friends = []
for _ in range(m):
    u, v = map(int, input().split())
    friends.append((u, v))
ans = 0


def bt(used, idx):
    global ans
    if idx == m:
        if len(used) < n:
            ans = max(ans, len(used)+1)
        else:
            print(n)
            exit()
        return
    # idx번째 참가
    if friends[idx][0] not in used and friends[idx][1] not in used:
        used.add(friends[idx][0])
        used.add(friends[idx][1])
        bt(used, idx+1)
        used.remove(friends[idx][0])
        used.remove(friends[idx][1])
    # idx번째 참가 X
    bt(used, idx+1)


bt(set(), 0)
print(ans)

 

입력으로 받은 친한 친구 관계 friends에서 각 원소의 커플을 넣는다/넣지 않는다 2가지 경우로 나눠서 탐색하면 된다. 예를 들어서 친한 친구 관계 (1, 2)가 있다고 할 때 1과 2가 같이 춤을 출 지, 안 출 지로 나누는 것이다.

만약 같이 출 것이라면 이 커플의 2명 다 아직 참석이 확정되지 않았는지 확인하고, 아직 둘 다 참석하지 않아서 참석이 가능하다면 이미 참석이 확정된 사람들의 집합인 used에 add해주고 bt함수를 재귀호출해준다. 이 bt 함수가 리턴될 때는 used에서 이 커플도 remove해줘야 한다. 그리고 같이 추지 않는 경우에는 used를 건드리지 않고 그냥 bt를 재귀호출해주면 된다.