[백준] 14889번 스타트와 링크- 파이썬(Python)

문제

• N(2의 배수)명의 사람들이 1번 부터 N번 까지 숫자가 배정 되어 있다.
• 이 N명의 사람들을 N/2명으로 이뤄진 2개의 팀으로 나눈다.
• i번째 사람과 j번째 사람이 같은 팀에 속해 있을때 능력치 $S_{ij}$가 팀에 능력치에 더해진다.
• $S_{ij}$는 $S_{ji}$와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 $S_{ij}$와 $S_{ji}$이다.
• 두 팀의 능력치의 차이의 최솟값을 구하는것이 문제이다

입력

• 첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다
• 둘째 줄부터 N개의 줄에 S가 주어진다

출력

• 두 팀간의 능력치 차이의 최솟값을 출력한다.
  

풀이

접근방법

• 백트래킹 알고리즘을 사용하여 문제를 접근하였다.
• 팀을 나눌때 N/2개의 index를 이용하여 팀을 구성하는 것을 생각했다.
• 편의상 문제에서는 1번 부터 번호를 매겼지만, 풀이에서는 0부터 이용한다.
• 이 때, 중복되지 않게 팀을 나누는것을 생각했다.

  ex) 6명이 있을 때 [0,1,2]로 팀을 구성하는 것과 [3,4,5]로 팀을 구성하는 것은 동일하다. 왜냐하면 한 팀이 결정되며 또 다른 팀은 자동으로 결정 되기 때문이다.

1. 팀을 나누는 경우의 수를 구하고 팀이 다 맞춰졌다면, 팀 능력 차이를 저장하는 함수(DFS)

def dfs(team_list):
	'''
    사전순으로 증가하는 수열을 구할 때 사용되는 dfs 사용하였다.
    '''
    if len(team_list) == N/2:
        cal_diff(team_list) # 사람들의 idx로 팀간 능력의 차이를 구하고 정답 리스트에 저장
        return None
    
    for i in range(team_list[-1]+1 if team_list else 0, N):
        if team_list and team_list[0] != 0:
          return None
        # if i not in team_list:
        team_list.append(i)
        dfs(team_list)
        team_list.pop()

• range(team_list[-1]+1 if team_list else 0, N)을 통해 사전순으로 증가하는 경우로 N/2개의 인덱스(사람들의 번호)를 순차적으로 뽑으면 팀을 나누는 모든 경우의 수를 구할 수 있다.

  팀을 구성할 때 뽑히는 순서가 상관없기 때문에 사전순으로 증가하는 방법을 통해 팀을 구성한다면 맨 뒤에 인덱스 다음 사람부터 고려하면 된다.

• 그러나 이 경우에 앞서 언급한 [0,1,2]와 [3,4,5]의 경우에 사실상 팀을 나눈 경우 동일하게 팀을 나눴다는것을 고려하지 못한다.
• 따라서 위의 경우의 수를 고려하기 위해 아래의 코드를 더하였다.

        if team_list and team_list[0] != 0:
          return

• N명의 사람들을 정확히 반으로 나누기 때문에 팀을 나눌 때 인덱스가 0번째인 사람은 무조건 어느 팀에든 들어가 있다.
• 그렇다면 0번째 사람을 포함하여 N/2명으로 이뤄진 팀을 구성하는 경우의 수만 구한다면 팀을 나누는 모든 경우의 수를 구한 것이다.(상대팀은 자동으로 결정되고 팀간의 구분이 없기 때문!)
• 그렇기 때문에 team_list에 index가 존재하는 경우에 무조건 첫번째 element는 0인 경우의 수만 구하면 된다! 그 외에는 return None 을 통해 dfs의 재귀를 종료한다.
• # if i not in team_list: << 사전순으로 증가하는 경우로 팀을 구성한다면 i가 리스트에 있는지 없는지 판단할 필요가 없다!

2. 주어진 인덱스 리스트로 두 팀간의 능력차이를 구하는 함수

def cal_diff(team_list: list) -> None:
    another_team_list = list(set(range(N)) - set(team_list)) 
    team_sum = 0
    for i, v in enumerate(team_list[:-1]):
        for v2 in team_list[i+1:]:
            team_sum += ability[v][v2] + ability[v2][v] # S_ij + S_ji
    
    another_team_sum = 0
    for i, v in enumerate(another_team_list[:-1]):
        for v2 in another_team_list[i+1:]:
            another_team_sum += ability[v][v2] + ability[v2][v]
    
    ans.append(abs(team_sum - another_team_sum))

    return None

• set 자료구조를 통해 입력된 팀 선수들의 인덱스로 부터 상대팀의 선수들의 인덱스를 구한다.
• ans 두 팀간의 능력 차이를 저장하는 리스트(global)

전체 코드

from sys import stdin
def cal_diff(team_list: list) -> None:
    another_team_list = list(set(range(N)) - set(team_list))
    team_sum = 0
    for i, v in enumerate(team_list[:-1]):
        for v2 in team_list[i+1:]:
            team_sum += ability[v][v2] + ability[v2][v]
    
    another_team_sum = 0
    for i, v in enumerate(another_team_list[:-1]):
        for v2 in another_team_list[i+1:]:
            another_team_sum += ability[v][v2] + ability[v2][v]
    
    ans.append(abs(team_sum - another_team_sum))

    return None


def dfs(team_list: list) -> None:
    if len(team_list) == N/2:
        cal_diff(team_list)
        return None
    
    for i in range(team_list[-1] if team_list else 0, N):
        if team_list and team_list[0] != 0:
          return None
        if i not in team_list:
            team_list.append(i)
            dfs(team_list)
            team_list.pop()

N = int(stdin.readline())
ability = [list(map(int, stdin.readline().split())) for _ in range(N)]
ans = []
dfs([])
print(min(ans))

결과

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