wip: 백준 14889번 스타트와 링크 파이썬 ( 실버 3, 백트래킹 )

2020년 12월 20일

시간초과난 풀이이다. 내가 틀렸다고 생각이 되진 않지만, 백트래킹이라는 단원에 답게 dfs 를 사용해 풀어야하는 문제임을 생각한다. 다시 풀자.

import collections
import itertools
N = int(input())
maps = [[]]*N
for i in range(N):
    maps[i]= list(map(int,input().split()))
history=[]
answer = 999999999999999999999999999999999999999999999999999999999
counts  =list(itertools.combinations(list(range(N)),N//2))
for count in counts:
    count = set(count)
    if count  in history:
        continue
    total = set(list(range(N)))
    reverse_count = total  - count
    history.append(count)
    history.append(reverse_count)
    
    count_cost = sum(list(map(lambda x:maps[x[0]][x[1]],list(itertools.permutations(count,2)))))
    reverse_cost = sum(list(map(lambda x:maps[x[0]][x[1]],list(itertools.permutations(reverse_count,2)))))
    answer=min(answer, abs(count_cost-reverse_cost))
print(answer)