[백준/파이썬] 14889번: 스타트와 링크

문제

풀이

백트래킹을 사용하여 팀간 선수들의 능력치 차이를 최소화하는 문제
visited를 두 팀 선수 배정에 사용

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    visited = [False] * n
    res = 1e9

선수 배정

	else: # 선발된 선수가 전체 인원의 절반이 아닐 경우
        for i in range(idx,n):
            if not visited[i]:
                visited[i] = True # i번 선수를 start 선수로 배정
                dfs(a+1, i+1) # 인원 +1, i번 이후 선수를 이용해 재귀
                visited[i] = False

선수가 전체 인원의 절반일 경우 능력치 차이 계산

	if a == n//2:
        start,link = 0,0 # 팀별 능력치
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    start += arr[i][j]
                elif not visited[i] and not visited[j]:
                    link += arr[i][j]
        res = min(res, abs(start-link)) # 팀별 능력치 차이 계산
        return

코드

import sys
input = sys.stdin.readline

def dfs(a,idx):
    global res
    if a == n//2:
        start,link = 0,0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    start += arr[i][j]
                elif not visited[i] and not visited[j]:
                    link += arr[i][j]
        res = min(res, abs(start-link))
        return
    else:
        for i in range(idx,n):
            if not visited[i]:
                visited[i] = True
                dfs(a+1, i+1)
                visited[i] = False


if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    visited = [False] * n
    res = 1e9

    dfs(0,0)
    print(res)