[백준/파이썬] 14889

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

스타트와 링크(삼성 SW 역량 테스트 기출 문제 2) - 실버 1

💫 알고리즘

백트래킹

후보 해를 한 단계씩 구축하며, 조건에 맞지 않는 경우 이전 단계로 되돌아가 다른 선택지를 탐색

깊이 우선 탐색(DFS)과 유사하며, 유망하지 않은 경로를 조기에 배제하여 탐색 효율을 높임

퍼즐, 조합 최적화, N-Queen 문제 등 복잡한 문제에서 가능한 해의 공간을 체계적으로 탐색

---

💡 풀이방향

🐢 백트래킹을 사용하여 모든 가능한 팀 조합을 탐색하며 차이 최소화

1️⃣ N명의 사람을 두 개의 팀(스타트 팀과 링크 팀)으로 나누어야 함

: DFS를 이용하여 N/2명의 스타트 팀을 선택하면 나머지는 자동으로 링크 팀

2️⃣ 팀 간 능력치 차이를 최소화

3️⃣ 팀의 능력치는 S[i][j] + S[j][i]

4️⃣ N은 짝수이며, N/2명씩 나누어야 함

5️⃣ 백트래킹(DFS)을 사용하여 가능한 모든 팀 조합 탐색하며 차이 최소화

: 모든 조합을 탐색하면서 |스타트 팀 - 링크 팀|의 최솟값을 저장

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
visited = [False] * N
result = sys.maxsize

def dfs(depth, idx):
    global result

    if depth == N // 2:
        start = 0
        link = 0

        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    start += S[i][j]
                elif not visited[i] and not visited[j]:
                    link += S[i][j]

        result = min(result, abs(start - link))
        return

    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            dfs(depth + 1, i + 1)
            visited[i] = False

dfs(0, 0)
print(result)

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

능력치 배열

visited = [False] * N

방문 여부; 스타트 팀과 링크 팀 구분을 위해

백트래킹(DFS): dfs함수

def dfs(depth, idx): #depth: 현재 선택한 스타트 팀원 수/ idx: 현재 탐색할 인덱스(중복 방지) 
    global result

    if depth == N // 2: # 팀 구분 완료
        start = 0
        link = 0

        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]: # 스타트 팀 능력치 합산
                    start += S[i][j]
                elif not visited[i] and not visited[j]: # 나머지(링크 팀) 능력치 합산
                    link += S[i][j]

        result = min(result, abs(start - link)) # 팀 능력치 차이 최솟값 갱신
        return

    for i in range(idx, N): # idx 이후부터 탐색(중복 방지)
        if not visited[i]: # 방문 X(팀 미정인 사람)
            visited[i] = True # 스타트 팀에 넣기
            dfs(depth + 1, i + 1) # 다음 사람 탐색
            visited[i] = False # 백트래킹(모든 경우의 수 탐색 위해 초기화)

🤔 visited 리스트로 어떻게 팀을 구분하는 건가요? 

🐢 간단하게 생각하시면 돼요. N/2명의 사람이 스타트 팀이 되면, 자동으로 나머지 사람들은 링크 팀이 되겠죠? visited[i] = True인 사람은 스타트 팀이, visited[i] = False인 사람은 링크 팀이 되는 거죠. 이에 따라 if-elif문을 두는 거고요.

---

🎁 더 보기

🐢 위의 문제는 조합으로도 풀 수 있습니다!

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

N = int(input())  
S = [list(map(int, input().split())) for _ in range(N)]  
result = float('inf')

# 모든 조합 탐색(N명 중 절반을 스타트 팀으로 선택)
for start in combinations(range(N), N // 2):
    link = list(set(range(N)) - set(start))  # 나머지가 자동으로 링크 팀

    # 스타트 팀과 링크 팀 능력치 계산
    start_stat = sum(S[i][j] + S[j][i] for i, j in combinations(start, 2))
    link_stat = sum(S[i][j] + S[j][i] for i, j in combinations(link, 2))

    # 최소 차이 갱신
    result = min(result, abs(start_stat - link_stat))

print(result)

for start in combinations(range(N), N // 2):

N명 중 N/2명을 뽑아 스타트 팀으로 만들고

link = list(set(range(N)) - set(start))

스타트 팀을 제외한 나머지가 링크 팀

start_stat = sum(S[i][j] + S[j][i] for i, j in combinations(start, 2))

link_stat = sum(S[i][j] + S[j][i] for i, j in combinations(link, 2))

팀 내에서 두 명을 뽑는 모든 조합의 능력치 합

🐢 combinations는 조합을 미리 생성하여 불필요한 연산 없이 팀을 나눌 수 있고, 최적화가 되어 있어 훨씬 빨라요!!