백준 15661 : 링크와 스타트 (파이썬)

정답코드

import sys

N = int(sys.stdin.readline())
arr = []
for i in range(N):
    arr.append(list(map(int, sys.stdin.readline().split())))

v = [False for i in range(N)]
temp = []
ans = 987654321


def dfs(start, cnt):
    global ans
    if cnt == N // 2:
        teamA = 0
        for i in temp:
            for j in temp:
                teamA += arr[i][j]

        temp2 = []
        for i in range(N):
            if i in temp:
                continue
            temp2.append(i)

        teamB = 0
        for i in temp2:
            for j in temp2:
                teamB += arr[i][j]
        if abs(teamB - teamA) < ans:
            ans = abs(teamB - teamA)
        return

    for i in range(start, N):
        if not v[i]:
            v[i] = True
            temp.append(i)
            dfs(i + 1, cnt + 1)
            temp.pop()
            v[i] = False

for k in range(0, N - 1):
    dfs(0, k)

print(ans)

문제유형

백트랙킹(DFS)