백준 14889번: 스타트와 링크 python

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

문제 이해

visited 배열을 사용해서 어떤 사람이 스타트 팀에 들어갔는지 표시.
DFS를 통해 스타트 팀의 구성원을 n/2명 뽑음.
다 뽑았으면 나머지 인원은 자동으로 링크 팀이 됨.
두 팀의 시너지 합을 계산해서 차이를 구하고, 최솟값 갱신.

코드 및 풀이

import sys
input = sys.stdin.readline  # 빠른 입력 처리

# 전체 인원 수 (짝수)
n = int(input())

# 능력치 테이블 입력받기 (2차원 배열)
s = [list(map(int, input().split())) for _ in range(n)]

# 각 사람의 팀 소속 여부를 기록하는 배열 (True면 스타트 팀, False면 링크 팀)
visited = [False] * n

# 두 팀 간 능력치 차이의 최소값을 저장할 변수 (처음엔 무한대로 초기화)
min_diff = float('inf')

# 팀의 시너지 합을 계산하는 함수
def get_score(team):
    score = 0  # 시너지 합
    for i in range(len(team)):
        for j in range(i + 1, len(team)):  # (i, j) 쌍 만들기
            a, b = team[i], team[j]
            score += s[a][b] + s[b][a]  # 시너지 합산
    return score  # 최종 합 리턴

# 백트래킹 DFS 함수
def dfs(depth, idx):
    global min_diff  # 바깥의 min_diff 사용

    # 스타트 팀에 n/2명을 다 뽑았다면
    if depth == n // 2:
        start_team = []  # 스타트 팀 구성원
        link_team = []   # 링크 팀 구성원
        for i in range(n):
            if visited[i]:  # visited[i] == True → 스타트 팀
                start_team.append(i)
            else:
                link_team.append(i)

        # 두 팀의 시너지 점수 계산
        start_score = get_score(start_team)
        link_score = get_score(link_team)

        # 점수 차이 계산
        diff = abs(start_score - link_score)

        # 최소값 갱신
        min_diff = min(min_diff, diff)
        return  # 종료

    # i는 idx부터 시작해서 중복 없이 조합을 만들도록 설정
    for i in range(idx, n):
        if not visited[i]:  # 아직 스타트 팀에 넣지 않은 사람이라면
            visited[i] = True  # i번 사람을 스타트 팀에 넣는다
            dfs(depth + 1, i + 1)  # 다음 단계로 재귀 호출 (depth 1 증가)
            visited[i] = False  # 백트래킹: 원상 복구

# DFS 탐색 시작
dfs(0, 0)

# 정답 출력
print(min_diff)