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

백준 14889 - 스타트와 링크

시간 제한 2초, 메모리 제한 512MB

# 조건

• 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다.
• 축구는 평일 오후에 하고 의무 참석도 아니다.
• 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다.
• 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
• BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다.
• 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.
• 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다.
• Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
• N=4이고, S가 아래와 같은 경우를 살펴보자.

• 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
  • 스타트 팀: S12 + S21 = 1 + 4 = 5
  • 링크 팀: S34 + S43 = 2 + 5 = 7
• 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
  • 스타트 팀: S13 + S31 = 2 + 7 = 9
  • 링크 팀: S24 + S42 = 6 + 4 = 10
• 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.
• 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

• 첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다.
• 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다.
• Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

• 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

# 접근 방법

• DFS와 백트래킹을 이용하여 풀어주면 된다.
• 주어진 입력을 받고 DFS 함수에 현재 인원수와, 번호를 넣어준다.
• 만약 현재가 절반의 인원을 한 쪽 팀에 구성했다면 => depth == n//2
  • 2중 반복문을 통해 visted 배열을 순회해준다.
  • 만약 i와 j가 같은 팀이라면 graph[i][j] 를 더해준다.
  • 둘 다 방문하지 않았다면 => 상대팀이라면 power2 에 더해준다.
• 모든 시너지를 더한 후 갱신해주면 된다.
• 이 때 백트래킹을 활용하여 현재 인원의 재귀가 끝난 뒤 다시 False로 방문 배열을 변경해주어야 모든 조합을 구할 수 있다.
• 또는 조합을 이용하여 절반만큼의 인원을 구성한 뒤, 제일 앞과 제일 뒤에서부터 start와 link팀을 각각 구성하며 구해줄 수도 있다.

def dfs(depth, idx):
    global min_diff
    if depth == n//2:
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    power1 += graph[i][j]
                elif not visited[i] and not visited[j]:
                    power2 += graph[i][j]
        min_diff = min(min_diff, abs(power1-power2))
        return

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

n = int(input())

visited = [False for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = int(1e9)

dfs(0, 0)
print(min_diff)