BruteForce19링크와스타트(15661)

문제

입력

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

출력

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

풀이

-index : 추가할 사람의 인덱스

• start : 스타트 팀
• link : 링크 팀
• 인덱스를 하나씩 증가시키면서 이 사람을 start 팀에 넣는 경우와 link 팀에 넣는 경우를 모두 체크한다.
• 만약 1번과 2번이 스타트 팀이라면,
• 스타트 팀 : S12+ S21 = 1 + 4 = 5
• 두 팀의 능력치 차가 최소로 될 때 return

코드

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline
# 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.!! 이 부분 해결 어려움
# start 팀을 선택하거나 선택하지 않으면서 집합을 구성한다
# 각 경우의 수에 대해 능력치 차이를 계산한다
# 가장 작은 차이를 출력한다
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

def go(index, start, link) : 
  if index == n :
    if len(start) == n or len(link) == n :
      return -1
    
    team_start = 0
    team_link = 0

    for i in range(len(start)) :
      for j in range(i+1, len(start)) :
        if i == j : continue
        team_start = team_start + s[start[i]][start[j]] + s[start[j]][start[i]]
    
    for i in range(len(link)) :
      for j in range(i+1, len(link)) :
        if i == j : continue
        team_link = team_link + s[link[i]][link[j]] + s[link[j]][link[i]]

    diff = abs(team_start - team_link)
    return diff
  
  if len(start) > n or len(link) > n : return -1

  ans = -1

	# index의 사람을 start 팀에 넣었을 때
  team_start = go(index+1, start+[index], link)
  if ans == -1 or (team_start != -1 and ans > team_start) :
    ans = team_start
  
	# index의 사람을 link 팀에 넣었을 때
  team_link = go(index+1, start, link+[index])
  if ans == -1 or (team_link != -1 and ans > team_link) :
    ans = team_link

  return ans

print(go(0,[],[]))

배운 것

• DFS 풀이