728x90
반응형
백준 14889번 스타트와 링크 (백트래킹)
1. 문제
두 팀으로 나누어 능력치의 합을 비교하는 문제이다. (n)명이 주어지면 이를 절반으로 나누어 두 팀을 구성하고, 두 팀의 능력치 차이를 최소화하는 것이 목표이다.
팀의 능력치는 각 팀에 속한 두 사람의 능력치의 합으로 계산된다. 즉, 두 사람이 같은 팀에 속했을 때 (S_{ij} + S_{ji})가 팀의 능력치로 더해진다.
2. 풀이
이 문제는 백트래킹을 이용해 모든 경우의 수를 탐색해서 최적의 값을 찾아야 하는 문제이다.
주어진 사람들을 두 팀으로 나누는 방법을 탐색하면서 팀의 능력치 차이를 계산한다.
문제 풀이 방법
- 백트래킹 함수 정의
- 사람들을 하나씩 선택하며 두 팀으로 나누는 과정을 탐색한다.
- (visited) 배열을 이용해 어떤 사람이 어느 팀에 포함되었는지 체크한다.
- 팀의 능력치 계산 함수 정의
- 주어진 팀을 인자로 받아서 팀원들 간의 모든 능력치 합을 계산한다.
- 모든 가능한 두 사람의 조합을 찾아서, 능력치를 더하는 방식으로 구현한다.
- 최솟값 비교 및 업데이트
- 모든 경우의 수를 탐색하면서 능력치 차이를 계산하여 최솟값을 업데이트한다.
3. 코드
import sys
input = sys.stdin.readline
n = int(input().rstrip())
s = [list(map(int, input().rstrip().split())) for _ in range(n)]
min_diff = float('inf')
team_size = n//2
visited = [False] * n
def teamPower(team):
power = 0
for i in range(len(team)):
for j in range(i+1, len(team)):
power += s[team[i]][team[j]] + s[team[j]][team[i]]
return power
def backtrack(idx, cnt):
global min_diff
if cnt == team_size:
team1, team2 = [], []
for i in range(n):
if visited[i]:
team1.append(i)
else:
team2.append(i)
power1 = teamPower(team1)
power2 = teamPower(team2)
min_diff = min(min_diff, abs(power1 - power2))
return
for i in range(idx, n):
if not visited[i]:
visited[i] = True
backtrack(i + 1, cnt + 1)
visited[i] = False
backtrack(0, 0)
print(min_diff)
입력 받기
n = int(input().rstrip())
s = [list(map(int, input().rstrip().split())) for _ in range(n)]- (n): 사람의 수.
- (s): 능력치 표. (s[i][j])는 사람 (i)와 (j)가 같은 팀일 때의 능력치.
팀 나누기
여기서는 visited 배열을 사용하여 팀을 나눈다. True는 팀1에 포함된 사람을, False는 팀2에 포함된 사람을 의미한다.
- visited 배열을 사용해서 팀에 포함된 사람을 표시한다. (True면 팀1에 속한 사람, False면 팀2에 속한 사람)
- backtrack 함수는 재귀적으로 호출되며, 각 사람을 팀1에 넣거나 넣지 않는 방식으로 모든 경우의 수를 탐색한다.
- cnt 변수를 이용해 현재 팀1에 포함된 사람의 수를 체크하고, 팀1의 인원이 n//2명이 되면 팀 나누기를 종료한다.
- 팀1과 팀2를 나눈 뒤, 각각의 능력치를 계산하고 차이를 비교하여 최솟값을 갱신한다.
team1, team2 = [], []
for i in range(n):
if visited[i]:
team1.append(i)
else:
team2.append(i)쉽게 말하면, 모든 사람을 한 명씩 팀1에 넣어보고 다시 빼면서 경우의 수를 모두 확인하는 방식이다.
팀의 능력치 계산 함수
def teamPower(team):
power = 0
for i in range(len(team)): # i는 현재 사람의 인덱스
for j in range(i + 1, len(team)): # j는 i보다 큰 인덱스만 탐색 (중복 방지)
power += s[team[i]][team[j]] + s[team[j]][team[i]]
return power- 팀의 모든 가능한 두 사람의 조합에 대해 (s[i][j] + s[j][i]) 값을 더하여 능력치를 계산한다.
S[3][4] + S[4][3] = 4 + 4 = 8
S[3][5] + S[5][3] = 5 + 4 = 9
S[4][5] + S[5][4] = 5 + 5 = 10
합계: 8 + 9 + 10 = 27
백트래킹 함수
def backtrack(idx, cnt):
global min_diff
if cnt == team_size:
team1, team2 = [], []
for i in range(n):
if visited[i]:
team1.append(i)
else:
team2.append(i)
power1 = teamPower(team1)
power2 = teamPower(team2)
min_diff = min(min_diff, abs(power1 - power2))
return
for i in range(idx, n):
if not visited[i]:
visited[i] = True
backtrack(i + 1, cnt + 1)
visited[i] = False- 현재 인덱스 (i)에서 사람을 선택하거나 선택하지 않는 방식으로 모든 경우를 탐색한다.
- 선택된 사람들로 팀을 구성한 후, (teamPower()) 함수로 능력치를 계산하여 최소 차이를 업데이트한다.
탐색 트리 예시
0 선택 → 1 선택 → 2 선택 → [0,1,2] vs [3,4,5]
↳ 3 선택 → [0,1,3] vs [2,4,5]
↳ 4 선택 → [0,1,4] vs [2,3,5]
↳ 5 선택 → [0,1,5] vs [2,3,4]
↳ 2 선택 → 3 선택 → [0,2,3] vs [1,4,5]
↳ 4 선택 → [0,2,4] vs [1,3,5]
↳ 5 선택 → [0,2,5] vs [1,3,4]
↳ 3 선택 → 4 선택 → [0,3,4] vs [1,2,5]
↳ 5 선택 → [0,3,5] vs [1,2,4]
↳ 4 선택 → 5 선택 → [0,4,5] vs [1,2,3]
4. 결과
💡 핵심 포인트
- 사람들을 두 팀으로 나누는 모든 경우의 수를 탐색하기 위해 백트래킹을 사용한다.
- 방문 체크 배열 (visited)을 사용하여 팀을 구분한다.
- 팀의 능력치 계산 함수는 (O(n^2))의 시간 복잡도를 가진다. (모든 두 사람의 조합을 확인하므로)
- 팀이 구성된 후 능력치 차이를 비교하여 최소값을 업데이트한다.
이 문제의 핵심은 모든 경우의 수를 탐색하되, 가지치기(pruning)를 잘하는 것이다. 백트래킹을 활용해서 효율적으로 풀 수 있다.
728x90
반응형