[백준 14889번] 스타트와 링크 - python

문제 링크

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

14889번: 스타트와 링크

풀이 

백트래킹 문제라고 생각하여, dfs로 풀어보았다. -> 그러나 시간초과 

dfs 변수로 선택한 사람의 수와 선택한 사람 번호가 담긴 set을 전달하는데,

선택한 사람의 수가 n//2 이면 점수차이를 계산해주었다. 

# 시간 초과 코드 
n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

def cal(s):
    num1 = 0
    num2 = 0

    for i in range(n):
        for j in range(n):
        	# 같은 팀이면 
            if i in s and j in s:
                num1 += graph[i][j]
            if i not in s and j not in s:
                num2 += graph[i][j]

    return abs(num1-num2)

visited = [False] * n
ans = int(1e9)

def dfs(cnt, s):
    global ans
    # n//2 명 뽑았으면 점수차이 계산 
    if cnt == n//2 :
        result = cal(s)
        ans = min(ans, result)
        return
	# 백트래킹 
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True
        s.add(i)
        dfs(cnt+1, s)
        s.remove(i)
        visited[i]=False

dfs(0,set())
print(ans)

이게.. 1,2,3,4 번의 사람이 있다고 했을 때 (1,2)가 선택된 경우와 (3,4)가 선택된 경우는 결과적으로 같은 경우인데 또 계산해서 그런 것 같다... 조합으로 풀어보았다. 

조합도 combinations 라이브러리를 사용하지 않고, 함수로 구현했다. 통과 ! 

# 조합 구하기 
def comb(arr, n):
    result = []

    if n > len(arr):
        return result

    if n == 1:
        for i in range(len(arr)):
            result.append([arr[i]])
    elif n> 1 :
        for i in range(len(arr)-n+1):
            for j in comb(arr[i+1:], n-1):
                result.append([arr[i]]+j)

    return result

# 점수 구하기 
def cal(s):
    num = 0
    for i in s :
        for j in s :
            if i == j:
                continue
            num += graph[i][j]

    return num
    
n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

arr = [ i for i in range(n)]

# n//2개만 구하면 된다. 속하지 않은 사람이 나머지 팀 
combine = comb(arr, n//2)
ans = int(1e9)

for c in combine:

    tmp = [ i for i in range(n)]
	# 상대팀구하기 
    for i in c:
        tmp.remove(i)

    num1 = cal(c)
    num2 = cal(tmp)
    ans = min(ans, abs(num1-num2))

print(ans)