[Python] 백준 - 스타드와 링크 14889

---

배경

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

14889번: 스타트와 링크

 

 

코드

def DFS(L, idx):
    global res
    if L==n//2:
        A=0
        B=0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    A += board[i][j]
                elif not visited[i] and not visited[j]:
                    B += board[i][j]
        res=min(res, abs(A-B))
        return
    for i in range(idx, n):
        visited[i]=True
        DFS(L+1, i+1)
        visited[i]=False
            

n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
visited = [0] *n
res = 2147000000
DFS(0,0)
print(res)

 

 

설명

N-Queen과 마찬가지로 visited[i]를 사용해서 해당 열의 index를 모두 순회해줍니다

L이 총 인원수의 //2배가 되면 체크를 시작합니다

해당 자신과 팀원이 같은 팀(True)라면 board에 더해주면서 체크하시면 됩니다

 

 

배운 점