[백트래킹] 스타트와 링크

오랜만에 백준 포스팅을 한다.

 

천천히 진행되던 백트래킹이 드디어 끝났다.

 

14889번: 스타트와 링크

from sys import stdin
from itertools import combinations as cb

N = int(stdin.readline())

ARR = []


def get_team_status(team_list: list):
    total = 0
    global ARR
    for x, y in cb(team_list, 2):
        total = total + ARR[x - 1][y - 1] + ARR[y - 1][x - 1]
    return total


for x in range(N):
    LINE = list(map(int, list(stdin.readline().split())))
    ARR.append(LINE)

team_combination = []

for i in cb(range(1, N + 1), int(N / 2)):
    team_combination.append(list(i))

min = 100

for j in range(int(len(team_combination) / 2)):
    if min == 0:
        break
    team_start = team_combination[j]
    team_link = team_combination[len(team_combination) - j - 1]
    min_now = abs(get_team_status(team_start) - get_team_status(team_link))
    if min_now < min:
        min = min_now

print(min)