백준 14889번 | 실버 1 | 스타트와 링크 | Python

kimminjunnn·2025년 11월 8일

백준 알고리즘

알고리즘

목록 보기

228/322

문제 출처: https://www.acmicpc.net/problem/14889

문제 파악

N명의 사람을 두 팀으로 나누었을 때,
각 팀의 능력치 차이가 최소가 되도록 하는 값을 구하는 문제다.

팀의 능력치는 팀에 속한 모든 두 사람 (i, j)에 대해
S[i][j] + S[j][i]의 합으로 계산된다.

1. 완전탐색 가능성 판단

N의 최댓값은 20이다.
한 팀을 N/2명씩 고를 때 가능한 조합의 수는
20C10 = 184,756 → 완전탐색으로 충분히 가능하다.

2. 팀 구성

itertools.combinations를 사용해 N명 중 절반을 고른다.
나머지는 차집합으로 상대 팀을 구성한다.
예:
(1, 2, 3)을 고르면 상대팀은 (4, 5, 6)이 된다.

3. 팀 능력치 계산

같은 팀 내에서 2명씩 조합을 만들어 능력치를 더한다.
combinations(team, 2)로 (i, j)쌍을 만들어
S[i-1][j-1] + S[j-1][i-1]을 누적한다.

4. 결과 갱신

두 팀 능력치 차이의 절댓값을 구하고
최소값을 계속 갱신한다.

조합을 활용한 해답 및 풀이

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input()) # 사람 수, 최대 20
S = []
for i in range(N):
    row = list(map(int,input().split()))
    S.append(row)
# S = [[0, 1, 2, 3], 
    # [4, 0, 5, 6], 
    # [7, 1, 0, 2], 
    # [3, 4, 5, 0]]

# 완전탐색 가능한지
# 20C10 = 184756
# 가능. 완전탐색으로 풀자

# # (1,2,3) / (4,5,6) 팀이면 팀 능력치는
# # S12+S21+S13+S31+S23+S32
# # vs
# S45+S54+S46+S64+S56+S65

# 1. 팀 NC(N/2) 로 팀 나누기
people = set(i for i in range(1,N+1)) # 집합 (1,2,3,...,N) 집합으로 한 이유는 밑에서 차집합을 활용하기 위해
min_diff = float('inf')

for team_start in combinations(people,N//2):
    team_link = list(people - set(team_start))

    # 2. 팀 능력치 구하기

    power_start = 0
    power_link = 0
    
    #또 팀 내에서 2명씩 뽑아서 능력치를 더해준다
    for i, j in combinations(team_start, 2):
        power_start += S[i-1][j-1] + S[j-1][i-1]

    for j, i in combinations(team_link, 2):
        power_link += S[i-1][j-1] + S[j-1][i-1]    


    # 차이의 최솟값을 계속 갱신하기
    diff = abs(power_start - power_link)
    min_diff = min(min_diff, diff)

print(min_diff)

그런데 사실 이 문제 백준에서 백트래킹으로 분류되어 있는 문제이기도 하다.

어떻게 백트래킹으로 풀 수 있을까?

1. visited 배열로 각 사람이 어느 팀에 속했는지 표시한다.

True → 스타트팀
False → 링크팀

2. dfs(depth, idx)

depth: 현재까지 선택한 스타트팀 인원 수
idx: 탐색을 시작할 다음 사람의 번호 (중복 방지)

3. 팀이 절반(N/2)명이 되면

→ 나머지는 자동으로 링크팀이므로
두 팀의 능력치 차이를 계산한다.

4. 최소값을 계속 갱신한다.

백트래킹 해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())

S = []
for i in range(N):
    row = list(map(int,input().split()))
    S.append(row)

result = 1e9
team_start = [False] * N # [False,False....False] N 인원수 만큼

def dfs(start_num,idx): # start_num = 현재까지 팀 스타트 인원 수, idx = 탐색을 시작할 다음 사람의 번호
    global result
    # 종료조건
    # 팀이 다 나눠지면
    if start_num == N/2:
        # 능력치 차이 계산
        power_start = 0
        power_link = 0

        for i in range(N):
            for j in range(N):
                if team_start[i] and team_start[j]:
                    power_start += S[i][j]

                elif not team_start[i] and not team_start[j]:
                    power_link += S[i][j]
        
        result = min(result,abs(power_start - power_link))
        return
                
    # 팀이 다 아직 안나눠졌으면 계속 나누기
    else:
        for i in range(idx,N):
            if not team_start[i]:
                team_start[i] = True 
                dfs(start_num+1,i+1)
                team_start[i] = False


dfs(0,0)
print(result)

team_start, team_link 를 True,False로.

        for i in range(N):
            for j in range(N):
                if team_start[i] and team_start[j]:
                    power_start += S[i][j]

                elif not team_start[i] and not team_start[j]:
                    power_link += S[i][j]

를 통해 능력치를 더한다는 발상이 획기적이었다.