15270(친구 팰린드롬) - 해결

친구 팰린드롬

 

문제

초등학생인 재홍이는 이번 봄 학예회 때, 재홍이가 지휘를 맡고 반 친구들이 춤을 추기로 계획했다. 이 춤은 시작할 때 춤추는 친구들이 일렬로 쭉 서서 각자 막춤을 추다가, 가운데 있는 친구를 기준으로 왼쪽과 오른쪽에 있던 친구들이 두손을 마주잡고 춤을 춘다. 즉 5명의 친구가 일렬로 서있었다면, 첫 번째 친구와 다섯 번째 친구가 함께 춤을 추게 되며, 두 번째 친구와 네 번째 친구가 함께 춤을 추게 된다. 세 번째에 있던 친구는 같이 출 수 있는 친구가 없기 때문에 혼자 로봇 댄스를 춘다.

재홍이네 반 친구들은 모두 자신과 친한 친구하고만 춤을 추고 싶어한다. 재홍이는 이번 학예회에 스케일 크게 해보고 싶기 때문에 최대한 많은 친구를 무대에 세우려고 한다. 친구 관계도가 주어졌을 때, 최대 몇 명을 무대로 올려보낼 수 있는지 구해서 재홍이에게 알려주자. 친구들은 출석번호로 나타내며, 1부터 시작해서 N까지 있다. 각 친구는 오로지 하나의 출석번호를 갖는다.

A와 B가 친한 친구고, B와 C가 친한 친구라고해서 반드시 A와 C가 친한 친구는 아니다. 로봇 댄스를 추는 친구를 제외한 무대에 올라가는 친구들은 모두 각자 자신과 친한 친구하고만 춤을 춰야한다. 또한 재홍이 반 친구들은 모두 로봇 댄스를 출 수 있다.

입력

첫째 줄에 총 반친구 수 N(2<=N<=20, 재홍이 제외)와 관계도 수 M(0<=M<=(N^2-N)/2, 최대 50 제한)이 주어진다. 둘째 줄부터 M+1줄까지 친한 친구 관계는 출석번호 u, v로 나타나며 u와 v는 같지 않고, u와 v가 친한 친구라면 v와 u도 친한 친구다.

똑같은 입력은 두 번 이상 나오지 않는다. 가령 1 2 가 이미 나왔다면 1 2 또는 2 1는 입력으로 들어오지 않는다.

 

출력

무대에 최대한 세울 수 있는 친구의 수를 출력한다.

---

가장 먼저 생각한 것이 백트래킹.

인접리스트를 활용하여 각 친구마다 연결하고 연결해제하는 방법으로 백트래킹을 수행하고자 하였다.

처음에는 계속 틀렸다. 어디가 틀린지도 잘 몰랐으나 가지치기와 백트래킹 자체가 잘못되었다는 것을 파악하였다.

이미 연결했거나 친구가 없는 경우에는 친구로 넘어가는 걸 처음에 헷갈려서 구현을 못하였었다.

그리고 본인의 연결 유무를 친구와 연결했을때 해야하는데 그전에 미리하여서 다음으로 넘어가도 연결되어있는 것으로 저장되어 그 부분도 수정하였다.

그리고 연결을 하고 난 뒤에 다음 친구로 넘어가는 것도 해주었다.

 

import sys
input = sys.stdin.readline

def dfs(n):
    global max_f
    # 마지막 친구까지 왔을 때
    if n == N:
        # 방문을 한 것은 짝을 지은 것이기 때문에 
        # 이것으로 몇명인지 파악
        sum_f = sum(visit)
        # N이 아니라면 1명을 추가
        if sum_f != N:
            sum_f += 1
        if max_f < sum_f:
            max_f = sum_f
        return

    # 방문을 했거나 친구가 없으면 다음 친구로 이동
    if visit[n] or friends[n] == []:
        dfs(n+1)
        return
    # 친구들을 만나면서 짝을 지어준다.
    for next in friends[n]:
        # 이미 짝이 지어져있으면 다음 친구로
        if visit[next]:
            continue
        visit[n] = 1
        visit[next] = 1
        dfs(n+1)
        # 백트래킹
        visit[n] = 0
        visit[next] = 0
    # 다음 친구로
    dfs(n+1)

N, M = map(int,input().split())

# 방문
visit = [0] * (N+1)
# 인접리스트
friends = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int,input().split())
    friends[A].append(B)
    friends[B].append(A)

max_f = 0

dfs(1)
print(max_f)