[Python] 14889 스타트와 링크 풀이

itertools 적극활용 코테최적화 풀이입니다
매우빠름 아마도

# PROBLEM - 스타트와 링크
# TIER - S2
# NUMBER - 14889
# DATE - 2022-08-08 18:46
# IDEA - 백트래킹으로 품
import sys
from itertools import combinations
input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
all_members = [i for i in range(1, N+1)] # 모든 멤버의 수
answer = []  # 계산 결과를 담을 배열

start_comb = list(combinations(all_members, N//2))  # 얘는 이제 start팀 조합을 만들어줌
start_comb = start_comb[:len(start_comb)//2]  # 딱 정확하게 반으로 잘라서(짝수니까) 반복되는 경우 XX

for start in start_comb:
    # link팀은 이제 start팀에 없는 멤버들이니까 이런식으로 start에 없는 멤버 == link
    s_power, l_power = 0, 0

    link = [x for x in all_members if x not in list(start)]

    start_pair = list(combinations(start, 2))  # 팀별로 좌표 2개씩 짝지어줌
    link_pair = list(combinations(link, 2))

    for i in start_pair:  # 그렇게 짝지어준 좌표끼리 합산해주고
        s_power += graph[i[0]-1][i[1]-1] + graph[i[1]-1][i[0]-1]

    for j in link_pair:
        l_power += graph[j[0]-1][j[1]-1] + graph[j[1]-1][j[0]-1]

    answer.append(abs(s_power-l_power))  # 이 둘의 차이를 구해서 answer에 추가한 뒤에

print(min(answer))  # 차이중 최소값 출력