14889번 스타트와 링크 - 백 트래킹

 14889번 스타트와 링크

14889번: 스타트와 링크

문제의 이해

어떤 사람과 팀이 되느냐에 따라 능력치가 달라질 때 두 팀의 능력치 차이가 가장 적을 때 얼마인지 알아내는 문제다.

직관적으로 떠오르는 방법은 조합을 구하고 팀 1,2를 조합해서 최소값을 찾으면 되는 문제인데 백트래킹이 붙어 있어서 아마 안 되겠지 생각하며 해 보았는데 성공.

조합을 생각해 보면 한 팀만 구성하면 나머지 팀이 완성되기 때문에, 그리고 인원이 짝수인 것이 보장되기 때문에

$$n C (n/2) = \frac{n!}{(n/2)!(n-(n/2))!}$$

가지 방법을만들 수있다.

이런 조합을 만드는 라이브러리인 combinations로 조합을 만들고 조합을 순회하면서 점수차를 내는 브루투포스 코드다.

from itertools import combinations
from sys import stdin as si
n = int(si.readline())
stat = [list(map(int,line.split())) for line in si.readlines()]

# 팀 능력치 계산 함수
def calc_stat(team):
    return sum(stat[i][j] for i in team for j in team if i != j)

# 최소 차이 계산
min_diff = float('inf') #최소차를 구하기 위한 초기값
for team1 in combinations(range(n), n // 2): #모든 조합을 순회
    team2 = [x for x in range(n) if x not in team1] #팀1에 없는 사람은 팀2(집합으로 하는 게 나을 듯)
    diff = abs(calc_stat(team1) - calc_stat(team2)) #차이 값 구하기
    min_diff = min(min_diff, diff) #최소 차이값 갱신
print(min_diff) #결과 출력

 

하지만 주제가 백트래킹인데... 백트래킹을 공부하고 있으니까 백트래킹을 써야겠다.

from sys import stdin as si
n = int(si.readline())
stat = [list(map(int, line.split())) for line in si.readlines()]

def div_tm(stat, idx, t1, t2, min_diff):
    if idx == n:  # 모든 선수가 팀에 배정됨
        s1 = sum(stat[i][j] for i in t1 for j in t1 if i != j)
        s2 = sum(stat[i][j] for i in t2 for j in t2 if i != j)
        return min(abs(s1 - s2), min_diff)
    
    if len(t1) < n // 2:
        min_diff = min(min_diff, div_tm(stat, idx + 1, t1 + [idx], t2, min_diff))
    
    if len(t2) < n // 2:
        min_diff = min(min_diff, div_tm(stat, idx + 1, t1, t2 + [idx], min_diff))
    
    return min_diff

print(div_tm(stat, 0, [], [], float('inf')))

div_tm 함수는 재귀적으로 모든 가능한 팀 조합 생성, 각 조합에 대한 능력치 차이를 계산
idx: 현재 고려하고 있는 선수의 인덱스
t1, t2: 현재까지 구성된 두 팀의 선수 인덱스 목록
min_diff: 현재까지 발견된 최소 능력치 차이입니다. 초기값 float('inf')로 설정

 

재귀적 탐색:
재귀의 초기 사례로, 모든 선수가 팀에 배정되었을 때(idx == n, 고려하는 선수 인덱스가 n과 같을 때) 두 팀의 능력치 합(s1, s2)을 계산하고, 이들의 차이를 min_diff와 비교하여 더 작은 값을 min_diff로 업데이트
idx번째 선수를 팀 1(t1)에 추가하는 경우와 팀 2(t2)에 추가하는 경우를 각각 탐색. 이때, 한 팀에는 최대 n/2명의 선수만 포함.
각 경우에 대해 재귀적으로 div_tm 함수를 호출, min_diff를 업데이트하여 가장 작은 능력치 차이를 찾기.

 

백트래킹:

백트래킹은 가능한 모든 해를 시도해보지만, 불필요한 경우의 수를 조기에 배제함으로써 효율성을 높일 수 있는 전략.