BAEKJOON-14889 : 스타트 링크

BEAKJOON-14889 : 스타트 링크

백트랙킹 문제를 여러 번 풀어봤다면 쉽게 풀 수 있는 문제이다.

시간단축을 위해 set 자료구조를 이용했다.

코드

n = int(input())
arr = [list(map(int,input().split()))[:n] for _ in range(n)]
teamA = []
teamAll = {i for i in range(n)}
cur_idx = 0
minV = 1000

def exp(team):
    s = 0
    for i in team:
        for j in team:
            s += arr[i][j]
    return s

def dfs(depth, cur_idx):
    global n
    global minV

    if depth == n//2-1:
        teamB = teamAll - set(teamA)
        expA = exp(teamA)
        expB = exp(teamB)
        minV = min(minV, abs(expA-expB))
        return
    
    for i in range(cur_idx+1, n):
        teamA.append(i)
        dfs(depth+1, i)
        teamA.pop()

teamA.append(cur_idx)
dfs(0, cur_idx)
print(minV)

exp함수는 팀의 능력치를 계산해주는 함수이다.

깊이 0, 인덱스 0부터 탐색을 시작한다.

팀 인원수는 n//2이기 때문에 깊이가 n//2라면 탐색을 멈추고, 각 팀의 능력치 차이를 구해서 최소값을 저장한다.

링크팀(teamB)를 구하기위해 집합 {0,..,n-1}에서 탐색해서 구했던 스타트팀(teamA)을 set구조로 바꾼뒤 차집합 연산을 해준다.

처음 탐색을 할 때, 0부터 n-1까지 탐색을 하지않고 0만 해준 이유는

i가 0일때의 팀 조합을 구한다면 나머지 1부터 n-1의 조합은 teamB에서 구해지기 때문이다