[백준][20단계 백트래킹] 14889번 /스타트와 링크 (파이썬/Python)

1. 문제 설명

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

2. 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input().strip())
S = [list(map(int,input().split())) for _ in range(N)]

pair = [[0]*N for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        pair[i][j] = S[i][j] + S[j][i]

min_diff = float('inf')
selected = [False] * N

def calc(team):
    total = 0
    m = len(team)
    for i in range(m):
        for j in range(i+1,m):
            a = team[i]
            b = team[j]
            if a < b:
                total += pair[a][b]
            else:
                total += pair[b][a]
    return total

def dfs(idx, cnt):
    global min_diff
    
    if cnt == N // 2:
        start = [i for i in range(N) if selected[i]]
        link = [i for i in range(N) if not selected[i]]
        
        start_score = calc(start)
        link_score = calc(link)
        diff = abs(start_score - link_score)
        
        if diff == 0:
            print(0)
            sys.exit(0)
        if diff < min_diff:
            min_diff = diff
        return
    
    if idx == N:
        return
    if N - idx < (N // 2 - cnt):
        return
    
    selected[idx] = True
    dfs(idx + 1, cnt + 1)
    
    selected[idx] = False
    dfs(idx + 1, cnt)
dfs(0,0)
print(min_diff)

3. 풀이 과정

입력 행렬을 s로 받는다.

대각선 윗부분(i<J)만 돌면서 pair[i][j]를 만들어 둔다.

selected[i] 배열로 i번 사람이 스타트 팀에 들어갔는지 여부를 관리하면서 DFS(백트리킹)으로 스타트 팀 조합을 만든다.

스타트 팀이 N/2명이 되면 start 팀과 link 팀의 멤버를 나눈다.

calc(team) 함수에서 대각선 윗부분(i<j)만 이중 for문으로 돌며 시너지 합을 계산한다.

두 팀 능력치 차이를 계산해 0이면 바로 출력 후 sys.exit(0)로 종료하고 아니면 최소값을 갱신한다.

모든 조합을 본 뒤 최소값을 출력한다.

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심