[백준] 14889번: 스타트와 링크 (백트래킹)

 

조합으로 풀 수도 있었지만 백트래킹을 연습하기 위해 다음과 같이 풀었다.

import sys
input = sys.stdin.readline

def backtracking(idx, start):
    global min_diff
    if idx == number:
        start_sum, link_sum = 0, 0
        link_team = list(total - set(start_team))
        for i in range(number):
            for j in range(i+1, number):
                start_sum += graph[start_team[i]][start_team[j]] + graph[start_team[j]][start_team[i]]
                link_sum += graph[link_team[i]][link_team[j]] + graph[link_team[j]][link_team[i]]
        min_diff = min(min_diff, abs(start_sum - link_sum))
        return

    for i in range(start, n):
        if check[i]:
            continue
        check[i] = True
        start_team[idx] = i
        backtracking(idx+1, i+1)
        check[i] = False

if __name__ == '__main__':
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)]
    min_diff = float('Inf')
    total = set(range(0, n))
    number = n // 2
    start_team = [0] * number
    check = [False] * n
    backtracking(0, 0)
    print(min_diff)