Python - 스타트와 링크 (14889) 백트래킹

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

N과 M 문제를 응용한 문제인 것 같다.

배열에 따로 숫자를 넣지 않고도 빈도 배열을 활용하여 답을 낼 수 있다.

 

import sys
input = sys.stdin.readline
n = int(input().strip())
a = [[0] *(n + 1)]
for i in range(1,n+1):
    a.append(list(map(int, input().strip().split())))
    a[i].insert(0, 0)
ans = 0x7fffffff
freq = [0] * 101

def p(depth, idx):
    global n, ans
    if depth == n // 2:
        s1 = s2 = 0
        for x in range(1, n + 1):
            for y in range(1, n + 1):
                if not (freq[x] or freq[y]): s1 += a[x][y]
                if freq[x] and freq[y] : s2 += a[x][y]
        ans = min(ans, abs(s1 - s2))
        return
    for i in range(idx, n + 1):
        freq[i] = 1
        p(depth + 1, i + 1)
        freq[i] = 0
            
p(0, 1)
print(ans)