[백준 | 실버3] 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는 입력으로 들어오지 않는다.

출력

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

예제 입력 1 복사

3 3
1 2
2 3
3 1

예제 출력 1 복사

3

예제 입력 2 복사

20 0

예제 출력 2 복사

1

예제 입력 3 복사

6 5
1 2
2 3
3 4
4 5
5 6

 

문제해설

시작할 때 춤추는 친구들이 일렬로 쭉
가운데 있는 친구를 기준으로 왼쪽과 오른쪽에 있던 친구들이 두손을 마주잡고 춤
5명의 친구가 일렬로 서 있는 경우
첫 번째 친구와 다섯 번째 친구가 함께 춤
두 번째 친구와 네 번째 친구가 함께 춤
세번째 친구는 혼자 춤

최대 몇 명을 무대로 올려보낼 수 있는지 구하기
가운대 있는 친구를 제외한 무대에 올라가는 친구들은 모두 각자 자신과 친한 친구하고만 춤을 춰야한다

3 3 <-- 총 반친구 수 N, 관계도 수 M
1 2 < --- 친구 관계는 출석번호 u, v(u와 v는 같지 않고, u와 v가 친한 친구라면 v와 u도 친한 친구다.)
2 3
3 1

1은 2과, 2는 1과 친함
2는 3과, 3은 2과 친함
3은 1과, 1은 3과 친함

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

 

문제풀이

1부터 N까지 출석번호에 번호 존재함
n개 중에서 n개를 다 뽑고 순서를 정하는 경우 다 구하기
만들어진 수열이 팰린드롬인지 조사
for i in range(int(len(job_num) / 2)) :
        if job_num[i] != job_num[-i-1] :
팰린드롬이고 친한 친구인 경우 카운트
친한 친구는 [i][j], [j][i]가 리스트에 있는 경우 찾기
카운트 해서 최대값 갱신

 

시간초과

def solution():
    n, mateyness_n = map(int, input().split())

    if mateyness_n == 0 :
        return 1

    mateyness_list = []
    for i in range(mateyness_n) :
        a, b = map(int, input().split())
        mateyness_list.append([a, b])          #친한 친구 리스트 a, b 저장
        mateyness_list.append([b, a])          #친한 친구 리스트 b, a 저장

    make_list = []
    check = [False] + [False] * n                     #재방문 확인을 위한 체크 표    

    def DFS(L) :
        if L == n :
            count = 0
            for i in range(len(make_list) // 2) :
                if [make_list[i], make_list[-i-1]] in mateyness_list :  #팰린드롬 친구가 친함 리스트에 존재하는가
                    count += 2                                          #존재 하는 경우 카운트
            return count
        else :
            max_count = 0
            for i in range(1, n+1) :
                if check[i] is False :
                    check[i] = True
                    make_list.append(i)
                    child_max_count = DFS(L+1)
                    if max_count < child_max_count:
                        max_count = child_max_count
                    check[i] = False
                    make_list.pop()
            return max_count 

    count = DFS(0)
    if n % 2 == 0 :             #짝수인경우 그대로
        return count
    else :                      #홀수인경우 가운데 친구 있으니까 +1 더해줌
        return count+1


print(solution())

 

시간초과

import sys

def solution():
    n, mateyness_n = map(int, sys.stdin.readline().rstrip().split())

    if mateyness_n == 0 :
        return 1

    set_list = set()

    mateyness_list = []
    for i in range(mateyness_n) :
        a, b = map(int, sys.stdin.readline().rstrip().split())
        mateyness_list.append([a, b])          #친한 친구 리스트 a, b 저장
        mateyness_list.append([b, a])          #친한 친구 리스트 b, a 저장
        set_list.add(a)
        set_list.add(b)

    new_set = list(set_list)
    make_list = []

    def DFS(L) :
        if L == n :
            count = 0
            for i in range(len(make_list) // 2) :
                if [make_list[i], make_list[-i-1]] in mateyness_list :  #팰린드롬 친구가 친함 리스트에 존재하는가
                    count += 2                                          #존재 하는 경우 카운트
            return count
        max_count = 0

        for i in range(L, len(new_set)) :
            make_list.append(new_set[i])
            child_max_count = DFS(L+1)
            if max_count < child_max_count:
                max_count = child_max_count
            make_list.pop()
        return max_count 

    count = DFS(0)
    if n % 2 == 0 :             #짝수인경우 그대로
        return count
    else :                      #홀수인경우 가운데 친구 있으니까 +1 더해줌
        return count+1

print(solution())