[BaekJoon] 백준 알고리즘 14889번 / 스타트와 링크 / 백트래킹(DFS) / Python

 

import sys
sys.stdin = open( "input.txt", "r")

def dfs(depth, idx):

    global minValue
    team1, team2 = 0, 0
    if (depth == N//2):
        for i in range(N):
            for j in range(N):
                if chk[i] == True and chk[j] == True:
                    team1 += graph[i][j]
                elif not chk[i] and not chk[j]:
                    team2 += graph[i][j]
        minValue = min( minValue, abs( team1 - team2 ) )
        return

    for i in range(idx, N):
        if not ( chk[i] == True ):
            chk[i] = True
            dfs(depth + 1, i + 1 )
            chk[i] = False

minValue = 100
N = int(input())
chk = [False for _ in range(N)]
graph = [list(map(int, input().split())) for _ in range(N)]

dfs(0, 0)
print(minValue)