백준 14889 스타트와 링크 - Python

출처 : 

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

14889번: 스타트와 링크

풀이 

n = int(input())
mat = []
A = []
B = []
for _ in range(n):
    mat.append(list(map(int, input().split())))
    
ans = float('Inf')

def dfs(depth):
    global ans
    if depth == n//2:
        A_sum = 0
        B_sum = 0
        for i in range(n):
            if i not in A:
                B.append(i)
        for i in range(n//2 - 1):
            for j in range(i+1, n//2):
                A_sum += mat[A[i]][A[j]] + mat[A[j]][A[i]]
                B_sum += mat[B[i]][B[j]] + mat[B[j]][B[i]]
                
        diff = abs(A_sum - B_sum)
        if ans > diff :
            ans = diff
        # 계산이 끝나면 B팀은 초기화 시켜준다.
        B.clear()
        return 
    #DFS 시작
    for i in range(n):
        if i in A: continue
        if len(A) > 0 and A[len(A)-1] > i : continue
        A.append(i)
        dfs(depth + 1)
        A.pop()
        
dfs(0)
print(ans)

언제쯤 내 스스로 깔끔하게 풀 수 있을까... 문제를 풀 때 a팀 b팀을 나누고 그 나눈 순서대로 더해서 백트래킹을 하면된다는 것 까지는 생각했는데 몇 틱이 부족해서 실패한다.... 더 열심히 해야겠다...

 

간략한 힌트 풀이를 보자.

 

문제는 팀 두개로 인원을 나눈다음 각 팀 mat[1][2] + mat[2][1] 이런식으로 더해서 다른 팀과의 차이를 구한다.

그 때 그 차이는 최소값으로 저장해서 출력을 하면된다.

 

그러기 위해선 일단 백트래킹으로 팀원을 선발해야하는데 

예를 들어서 n = 6 이라면 

A = [1 ,4, 5] / [1,4,6]/[1,5,6] 이런식으로 계속 돌아가면서 경우의 수를 탐색해야한다. 

 

이제 위에부터 뜯어보겠다.

입출력 부분은 위와 같이 해서 행렬 형태로 받아 와준다. 

 

그리고 문제에서 필요한 A팀, B팀, 그리고 최솟값 ans 까지 초기화 선언 시켜준다.

 

이제 DFS를 보겠다.

백트래킹이니까 결과가 어떻게 나올 지 부터 생각해보자. 

dfs(depth)를 설정해준다음 depth가 A팀의 인원이 꽉 찼을 때 출력 과정을 실시해주고자 다음처럼 if depth==n//2 를 넣어줬다.

 

다음 A팀의 전력의 합과 B팀의 전력의 합을 A_sum , B_sum 으로 선언해준다.

 

그리고 for i in range(n) 을 돌려서 A에 없는 리스트를 B에 저장해준다.

 

그 다음은 A_sum, B_sum 을 구해야 한다.

A=[1,2,3] 이라면 

A_sum = 12 + 21 + 13+ 31 + 23+ 32  일 것이다. 

따라서 입출력에 넣은 행에서 12 와 13 그리고 23 의 과정을 더해주면 될 것이다. 

경우의 수를 생각하면서 하면 

for i in range(n//2 - 1): for j in range(i+1, n//2) 를 이해하기 편할 것이다. 

그렇게 A_sum += mat[A[i]][A[j]] + mat[A[j]][A[i]]  이렇게 계산해주고

diff = abs(A_sum - B_sum) 으로 최소값을 ans에 저장해주면서 이 과정이 끝나고 B.clear()를 사용해서 B를 초기화 시켜준다.

 

이제는 A팀을 정하는 경우의 수인데

이미 팀원으로 정해진 인덱스가 나오면 건너뛰어준다. 

그렇게 A에 팀원을 정해주고 dfs를 반복시켜서 팀원을 계속 추가해준다. 

dfs 과정이 끝나면 pop를 이용해 새로운 팀원이 들어올 수 있게 해준다. 

 

그렇게 dfs(0)을 출력하고 ans를 출력하고 마친다.